Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Hatpontú gráf

19
Rajzoljon egy olyan hatpontú gráfot amelyben a csúcsok fokszáma: 4, 4, 3, 2, 2, 1.
Jelenleg 1 felhasználó nézi ezt a kérdést.
#matek #gráf
0
Középiskola / Matematika

Válaszok

1
Többféle megoldási mód van az ilyen feladatoknál;

1) Az egyik az ún. Hakimi-algoritmus: https://hu.wikipedia.org/wiki/Havel%E2%80%93Hakimi-algoritmus
Bár bonyolultnak tűnik, valójában az eljárás nagyon egyszerű;
-kiválasztod a legnagyobb fokszámú csúcsot (ha több van, akkor mindegy, melyiket)
-összekötöd az össze többi legnagyobb fokszámúval (esetünkben az egyik 4-est a másik 4-essel, a 3-assal és a két 2-essel kell)
-visszalépsz az 1. lépésre.
Ezt addig csinálod, amíg nem tudsz minden élt behúzni. Ha megvan, akkor két lehetőség van; vagy jó a gráf, amit kaptál, vagy nem (tehát minden csúcshoz annyi él tartozik, amennyinek kell). Ha igen, akkor kész vagy, ha viszont nem (és nem rontottad el az eljárást), akkor azt látjuk, hogy ilyen gráf nem létezik (ugyanis ez az eljárás minden esetben ad megoldást, ha létezik), ellenben itt még be kell látni, hogy ezekkel a fokszámokkal nem létezhet gráf (most nem erről van szó, így erre nem térek ki).
A Hakimi-algoritmussal kirajzolható gráftól lényegesen eltérő gráf is rajzolható, ha nem csak egyféle gráf létezik az adott fokszámokkal.

2) A komplementergráf megrajzolásával;
Ha nem tudjuk azokat behúzni, amiket kérnek, akkor húzzuk be azokat, amiket nem kérnek! Eszerint a fokszámok így alakulnak: 1, 1, 2, 3, 3, 4. Itt nem egyszerűsödött lényegesen a feladat, de ezen egy kicsit egyszerűbb megcsinálni a 3)-ast.

3) A mindig "biztosra megyünk" elve szerint;
Itt is a nagy fokszámúak kerülnek előtérbe. Vegyük az egyik 4-est. Azt nem tudjuk, hogy melyikekkel kellene összekötni, de azt igen, hogy akárhogyan húzzuk be az éleket, valamelyik 2-es fog belőle kapni (mondjuk a skatulya-elvre való hivatkozással). Nosza, húzzuk be az egyikbe az élt, ekkor ez a számsor marad:
4, 3, 3, 2, 1, 1
Ugyanaz a történet, mint az előbb; az biztos, hogy valamelyik 3-as, és 1-es is fog a 4-es éleiből kapni, tehát (most 2 élt húzunk be, így a 4-ből 2 lesz):
2, 3, 2, 2, 1, 0
A 3-asból szintén jut biztosan valamelyik 2-esbe:
2, 2, 2, 1, 1, 0
Itt már sajnos nem tudjuk azt eljátszani, amit eddig, mert a 2-esből mehet csak a 2-esekbe is vagy csak az 1-esekbe, így bizotsat nem tudunk mondani. Ellenben a lehetősgek száma igencsak lecsökkent, így már nem nehéz befejezni.

Nézzük, hogy a komplementergráfnál mi a helyzet;
4, 3, 3, 2, 1, 1, ezzel a számsorral már találkoztunk, így le is vezettük.
Annyi a különbség, hogy ha ennek a végére jutunk, akkor nekünk pont azokra az élekre lesz szükség (mivel a komplementergráfot kezdtük el összetákolni), amiket nem húztunk be itt.
0