Hogyan kell megoldani ezt a gráfelmélet feladatot?
Figyelt kérdés
Egy 50 csúcsú egyszerű gráfban a maximális fokszám 7. Mutassuk meg, hogy
van a gráfban 7 csúcsú független ponthalmaz.
2022. máj. 23. 22:17
2/7 anonim 
válasza:
válasza:Indirekt feltesszük, hogy a maximális független csúcshalmaz legfeljebb 6. Ekkor felhasználva a maximális független csúcshalmaz azon tulajdonságát, hogy egy tetszőleges csúcs vagy a maximális független csúcshalmaz közé tartozik, vagy van olyan szomszédos csúcsa, amely oda tartozik, adódik az ellentmondás a fokszámra vonatkozó feltétel miatt, hiszen 6 + 6*7 = 48 < 50.
3/7 anonim 
válasza:
válasza:Itt ha jól értelmezem használni kell először Gallai 1. tételét miszerint n=alpha(G)+tau(G). A tau(G)-ből kijön hogy csak 1 pontnak létezik maximális fokszáma a többi mind izolált pont, hiszen kevesebbel nem tudjuk lefogni a gráf pontjait úgy hogy minimális maradjon tau(G). Így a gráfban valóban létezik 7 csúcsú független ponthalmaz.
4/7 A kérdező kommentje:
Köszi a válaszokat, és igen BSZ2 <3
2022. máj. 24. 01:05
5/7 A kérdező kommentje:
Köszi a segítséget 44/50 pontom lett a ZH-n.
2022. máj. 31. 21:07
7/7 A kérdező kommentje:
A bsz2 a BME-VIK mérnök info szakon egy tárgy. Bevezetés a számításelméletbe 2-t rövidíti. Ha érdekel írd be google-be, hogy vik wiki és ott a második féléves tárgyak között megtalálod.
2022. okt. 15. 15:44
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!