färgningsproblem med banker och direktörer
Minns ni den stora bankkrisen i början av 90-talet? Totalt fanns det k banker före krisen. Bank 1 hade direktörer, bank 2 hade d2 direktörer och så vidare. Totalt finns n direktörer. Varje direktör arbetar bara i en bank, så d1 + d2 +... + dk = n. När alla banker gått bankrutt beslutar regeringen att skapa ett nytt banksystem med nya banker. Samma direktörer anställs igen, men så att två direktörer som tidigare var på samma bank inte får hamna på samma nya bank. Visa att antalet sätt att för fixt n fördela direktörerna på de λ nya bankerna (utan restriktioner på hur många som hamnar på varje bank) är ett polynom λn + an-1 λn-1 + ... + a0, och att
(Tips! Se det som ett färgningsproblem. Vad är antalet kanter i en komplett graf med d hörn? Hur syns antalet kanter i det kromatiska polynomet?)
Antalet kanter i en komplett graf med d hörn är . Jag ser att det måste finnas ett samband mellan antalet kanter och problemet i sig men behöver lite mer tips för att kunna se sambandet tydligare. Kan ni hjälpa mig?
Tolkningen här är att vi har en graf som består av k kompletta delgrafer, varje delgraf är också isolerad från varje varje annan. Att denna graf sedan ska färgläggas med lambda färger.
Sedan ska vi visa 3 saker:
att antalet sätt att göra detta på är ett polynom i lambda
att polynomet är av grad n
att den första koefficenten i polynomet är (minus) antalet kanter i grafen.
Alla tre saker är kända egenskaper hos det kromatiska polynomet, så problemet består mest i att förklara tolkningen.
Smutsmunnen skrev:Tolkningen här är att vi har en graf som består av k kompletta delgrafer, varje delgraf är också isolerad från varje varje annan. Att denna graf sedan ska färgläggas med lambda färger.
Sedan ska vi visa 3 saker:
att antalet sätt att göra detta på är ett polynom i lambda
att polynomet är av grad n
att den första koefficenten i polynomet är (minus) antalet kanter i grafen.
Alla tre saker är kända egenskaper hos det kromatiska polynomet, så problemet består mest i att förklara tolkningen.
Tack för förklaringen! Jag har nu en lösning som är väldigt lång. Här kommer den:
Jamen jag tycker det ser ut att stämma.
