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ó
Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Rajzolható-e olyan ötpontú...

Rajzolható-e olyan ötpontú egyszerű gráf?

Figyelt kérdés

amelyben az egyes pontok fokszáma:

a; 1, 2, 2, 2, 3

b; 1, 1, 2, 2, 4

c; 1, 2, 3, 3, 4

d; 1, 3, 3, 4, 5

Hogyan lehet eldönteni hogy miből lehet gráfot rajzolni és miből nem?

Nagyon megköszönném a segítséget egy kis magyarázattal! :)



2016. máj. 28. 12:12
1 2
 11/14 anonim ***** válasza:

Legyen egy n csúcsú (létező egyszerű) gráf fokszámai a(1)>=a(2)>=...>=a(n), és nevezzük {a(1);a(2);...;a(k)} fokszámokkal rendelkező csúcsok halmazát nagy fokszámú csúcsok halmazának:=N, a többi a kis fokszámú csúcsok halmazát:=K jelölje. Ebben az esetben ha N-ben futó maximális élszám e(N), a két halmaz között futó élek száma e(N;K), akkor tetszőleges k-ra (1<=k<=n) e(N)+e(N;K)<=(a(1)+a(2)+...+a(n))/2, vagyis N-ben és N és K között futó élek száma legfeljebb annyi, mint az élek száma. Ha létezik k, hogy ez nem teljesül, akkor a számsorhoz nem létezik gráf (ez az ellenpélda, amit mondtam).


Ez a tétel használható a d) feladatban; ha k=3, akkor a nagy fokszámok: (3;4;5), ezek között legfeljebb 3 él futhat, a két ponthalmaz között legfeljebb 4 él futhat, tehát legfeljebb 7 élt tudunk behúzni a gráfba, viszont (5+4+3+3+1)/2=8 élünk van, tehát erre a számsorra nem létezik gráf (persze, az egyszerűbb, hogy az 5-ösből legfeljebb 4 élt tudunk húzni a másik négybe, és ezért nem nyerő ez a számsor, de bonyolultabb esetben ezt és így kell használni).


Remélem, sikerült meggyőznöm a nagyérdeműt.

2016. máj. 28. 19:26
Hasznos számodra ez a válasz?
 12/14 anonim ***** válasza:
Javaslom az "ellentmondás" és az "ellenpélda" szavak megkülönböztetését.
2016. máj. 28. 19:29
Hasznos számodra ez a válasz?
 13/14 anonim ***** válasza:

Ilyen kis fokszámoknál (de ez is általánosítható) a legmagasabb fokszámból érdemes kiindulni. Egy ötpontú egyszerű gráfban egy csúcs maximális foka négy (ez a d)-t kivégzi). A b) feladatban tekintsük azt a G' gráfot amiből a 4 fokszámú csúcsot és a belőle vezető éleket töröltük. Mivel minden ponttal össze volt kötve, minden csúcsnak eggyel csökken a fokszáma, 0,0,1,1 . A G' gráf tehát egyszerűen egy él és két pont. Addjunk hozzá egy ötödik pontot ami mind a négy ponttal össze van kötve, ez a keresett G gráf. Még az érettségiben is volt ilyen példa. Leírni tovább tart mint kigondolni :)


c) az páratlan, d) az 5 miatt nem lehet.


Az a) nagyon is létezik. Ha egy egyszerű gráfban nincsen kör akkor fa tehát van legalább két elsőfokú csúcsa és a)-ban csak egy van tehát van benne kör. Milyen hosszú lehet? Egy kör legalább 3 hosszú és egy 5 hosszú körnél minden pont fokszáma 2 lenne. Ha 3 hosszú akkor a többi él valahol csatlakozik a háromszöghöz, tehát a körön lévő egyik pont lesz 3 fokú, a másik kettő 2 fokú, tehát a 3-asból (legyen A) nem a háromszögbe indul egy él, legyen ez D, innen megint csak nem tudunk a háromszög pontjaihoz csatlakozni tehát a DE létezik és ez az egyik válasz: egy háromszög csúcsából induló 2 hosszú út. Ha a kör négy hosszú akkor egyszerűen látható hogy az ötödik pontot összekötve egyik csúccsal is pont megfelelőt kapunk.

2016. máj. 29. 12:46
Hasznos számodra ez a válasz?
 14/14 anonim ***** válasza:
Ps. [link] itt angolul van szép algoritmus és magyarázat.
2016. máj. 29. 12:49
Hasznos számodra ez a válasz?
1 2

Kapcsolódó kérdések:





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