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
 1/14 anonim ***** válasza:
Igen, igen, nem, nem. Ha igen, azt ilyen kicsi gráfnál legegyszerűbb úgy belátni, hogy lerajzolsz egyet. Ha nem, akkor meg kell keresni egy ellentmondást, ami miatt lehetetlen. Pl a fokszámok összege nem páros (c) vagy van a pontok száma-1-nél nagyobb fokszám (d).
2016. máj. 28. 12:36
Hasznos számodra ez a válasz?
 2/14 anonim ***** válasza:
Nagyobb csúcsszám és fokszám esetén úgy érdemes eljárni, hogy a legnagyobb fokszámút összekötöd a többi legnagyobb fokszámúval, de csak annyival, amennyi a fokszáma, utána a soron következő legnagyobbal megcsinálod ezt, és ezt addig csinálod, míg nem lesz összekötve mindegyik csúcs a megfelelő számban a többivel, ha pedig nem rontod el, és mégsem jön ki, akkor nincs ilyen gráf. Ezt Hakimi-algoritmusnak hívják.
2016. máj. 28. 13:55
Hasznos számodra ez a válasz?
 3/14 anonim ***** válasza:
Ha a Hakimi algoritmus elakad akkor még nem lehet arra következtetni, hogy nincs olyan gráf!
2016. máj. 28. 16:32
Hasznos számodra ez a válasz?
 4/14 anonim ***** válasza:
Ha nem rontja el, akkor tudunk ellenpéldát mutatni, szóval következik belőle...
2016. máj. 28. 16:45
Hasznos számodra ez a válasz?
 5/14 anonim ***** válasza:
Ha a Hakimi nem fut le, az valóban ekvivalens azzal, hogy nincs olyan gráf, de nem azért, mert ellenpéldát adna. Nemlétezést nem lehet ellenpéldával bizonyítani.
2016. máj. 28. 17:05
Hasznos számodra ez a válasz?
 6/14 anonim ***** válasza:
Rosszul fogalmaztam; ehhez kapcsolódóan tartozik egy tétel, arra tudunk egy ellenpéldát mutatni, hogy létezik egy olyan csúcselosztás, amire túl sok él van.
2016. máj. 28. 17:33
Hasznos számodra ez a válasz?
 7/14 anonim ***** válasza:
Ennek fuss neki még egyszer, mert így nincs értelme.
2016. máj. 28. 18:03
Hasznos számodra ez a válasz?
 8/14 anonim ***** válasza:
Miért is nincs? ...
2016. máj. 28. 18:45
Hasznos számodra ez a válasz?
 9/14 anonim ***** válasza:
Mert nem derül ki belőle, mit akarsz mondani. Amit leírtál, az azt jelenti, hogy van egy tétel, és erre a tételre te tudsz ellenpéldát (tehát nem igaz).
2016. máj. 28. 18:48
Hasznos számodra ez a válasz?
 10/14 anonim ***** válasza:
Vagy ha másképp tagolod, akkor valaminek a létezésére tudsz ellenpéldát mutatni, ami még nagyobb hülyeség.
2016. máj. 28. 18:55
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!