Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ

Főoldal Belépés/Regisztráció Egy véletlen kérdés Facebook






Kategória: Közoktatás, tanfolyamok » Házifeladat kérdések

A kérdés

Kombinatorika, Euler körös. Ez így jó?

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?



Keress kérdéseket hasonló témákban: matematika, gráfelmélet, kombinatorika

  dec. 3. 01:50  Privát üzenet  

A válaszok
A kérdező kommentje:

Ja és ez összefüggő gráf lesz. Trivi

# 1/4Időpont dec. 3. 01:57 Privát üzenet
Baluba nevű felhasználó 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.

A válaszíró 74%-ban hasznos válaszokat ad.
# 2/4Időpont dec. 3. 09:13 Privát üzenet
Hasznos számodra ez a válasz?
A kérdező kommentje:

Áh tényleg, összekevertem a kettőt! Akkor Dirac tétel miatt itt van H-kör. Kössz!

# 3/4Időpont dec. 4. 17:45 Privát üzenet
Baluba nevű felhasználó 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.

A válaszíró 74%-ban hasznos válaszokat ad.
# 4/4Időpont dec. 5. 09:40 Privát üzenet
Hasznos számodra ez a válasz?

Értesítsünk róla, ha új válasz érkezik? Válasz küldése



Kapcsolódó kérdések
Egzszerű kombinatorika. Hányféleképpen választhatunk ki 11 fehér és 5 vörös borból 5 palack bort úgy, hogy mindkét fajtából legalább 2 legyen? (tehát 2 vörösnek és 2 fehérnek kell lennie legalalább)
Ezt a kombinatorika feladatot hogy kell megoldani?
Hogy kell megoldani a következő kombinatorikai feladatot?
Matek OKTV jellegű kombinatorika feladat. Hogy oldjuk meg?
Hogyan lehet 90 számból 5-öt úgy kiválasztani, hogy ne legyen köztük szomszédos elem?
Hogyan lehet 90 számból 5-öt kiválasztani úgy, hogy ne legyen köztük szomszédos elem?

Kérdések a Közoktatás, tanfolyamok rovatbólKérdések a Házifeladat kérdések rovatból








Minden jog fenntartva © 2019, www.gyakorikerdesek.hu | GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | WebMinute Kft. | 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!