Gäster
Hej,
Jag har stött på följande problem:
Till en middag anländer 14 gäster. Var och en känner minst 7 andra av de närvarande (bekantskap anses vara en ömsesidig relation). Visa att personerna kan placeras runt ett bord så att varje gäst känner båda sina bordsgrannar.
Jag tänker att jag kan representera de 14 gästerna som 14 noder, och att vänskapen mellan dessa kan betecknas som en väg mellan två noder. Jag tänkte sedan att jag kan forma en cirkel som representerar bordet som knyter samman alla 14 noder. Om jag väljer en valfri nod, så har den redan två noder till sig, en till höger och en till vänster. Därefter har den fem noder kvar att kunna binda in till resterande 11 noder. Då kan varje gäst känna båda sina bordsgrannar, samtidigt som de kan känna minst 7 av de närvarande. Har jag tänkt rätt?
Tack på förhand!
Lite konstig uppgift. Eller tänker jag fel? Men det står ju "Var och en känner minst 7 andra"
Då kan jag väl säga att alla känner alla!? Då känner var och en 13 andra, dvs minst 7 andra.
larsolof skrev:Lite konstig uppgift. Eller tänker jag fel? Men det står ju "Var och en känner minst 7 andra"
Då kan jag väl säga att alla känner alla!? Då känner var och en 13 andra, dvs minst 7 andra.
Ja, uppgiften känns väldigt konstig i sig, det är nästan som om lösningen är självklar. Det är därför jag själv tvekar.
Du kan anta att varje person känner exakt 7 personer, om någon känner flera blir ingen lösning som gällde innan "förstörd".
Den är nog inte så självklar som du tänker dig. Hur vet du att det inte är så att personerna kommer tex från 2 klasser så att varje halva känner varandra allihop och alla känner en person från andra klassen? Om alla i klass A känner samma petson i klass B är det inte jättelätt att binda ihop cirkeln på båda sidor av bordet.
Själva frågan är om du alls kan få till en cirkel där alla noder är med, alltså en hamiltoncykel. Kolla om du har någon sats om när de finns i boken, kan inte tänka mig att man bevisar det från grunden på gymnasiet.
Micimacko skrev:Du kan anta att varje person känner exakt 7 personer, om någon känner flera blir ingen lösning som gällde innan "förstörd".
Den är nog inte så självklar som du tänker dig. Hur vet du att det inte är så att personerna kommer tex från 2 klasser så att varje halva känner varandra allihop och alla känner en person från andra klassen? Om alla i klass A känner samma petson i klass B är det inte jättelätt att binda ihop cirkeln på båda sidor av bordet.
Själva frågan är om du alls kan få till en cirkel där alla noder är med, alltså en hamiltoncykel. Kolla om du har någon sats om när de finns i boken, kan inte tänka mig att man bevisar det från grunden på gymnasiet.
Hur menar du med att få till en cirkel där alla noder är med? Om jag placerar 14 noder och drar 6 kanter från varje nod som representerar en vänskap, så behöver jag göra detta 7 gånger totalt, och får alltså 6 * 7 = 42 kanter.
Menar du att jag utifrån dessa kanter och noder sedan skall försöka hitta en Hamiltoncykel som går från ursprungspositionen genom alla noder max en gång och sedan tillbaka till ursprungspositionen. Hur kan man då direkt från bara antalet kanter och antalet noder avgöra om det går att bilda en Hamiltoncykel eller inte?
Jag hittar en sats som känns verka på rätt spår iallafall: "Meyniel (1973). A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to 2n − 1." (https://en.wikipedia.org/wiki/Hamiltonian_path).
Eller kanske den här? Din handlade om riktade grafer, det låter onödigt krångligt för det här.
