Kombinatorika, Euler körös. Ez így jó?
Figyelt kérdés
A feladat: 10 házaspár mindegyik tagjára igaz, hogy a másik 9 házaspár mindegyikének legalább az egyik tagját ismeri. Lássuk be, hogy ez a 20 fő leülthethető egy körasztalhoz úgy, hogy mindenki ismerje a szomszédját.(ismeretség kölcsönös, és házasságon belül ismerik egymást)
Megoldásom: Ha minden tag csak 9 másikat ismer, és +1, a saját párját, akkor a fokszám mindegyiknek 10. Ez páros, tehát van Euler kör, és ennek mentén az ülésrend jó. Ha több embert ismernek mint 9, az nem befolyásolja az előző Euler körnek a jóságát, ezért nem baj, ha 9-nél többet ismernek.
Ez így teljes megoldás?
2019. dec. 3. 01:50
1/4 A kérdező kommentje:
Ja és ez összefüggő gráf lesz. Trivi
2019. dec. 3. 01:57
2/4 Baluba 
válasza:
válasza:Neked nem Euler-kör hanem Hamilton-kör kell. De szerintem az Euler-kör létezésének bizonyításához használt gondolat (nem tudunk elakadni) itt is működik.
3/4 A kérdező kommentje:
Áh tényleg, összekevertem a kettőt! Akkor Dirac tétel miatt itt van H-kör. Kössz!
2019. dec. 4. 17:45
4/4 Baluba válasza:
válasza:A Dirac erre nem alkalmazható szeirntem módosítás nélkül, mert nem minden H kör megoldás, csak ha a házastársak egymás mellett ülnek. Ha meg összehúzod a házastársakat egy pontba, akkor nem egyértelmű, hogy mik az ismeretségi élek.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!