Eulerovský graf
Ahoj poradil by mi někdo z touto úlohou.
Trochu jsem pátral na internetu a zjistil jsem, že tedy eulerovský graf je graf, který je sudý. A dá se nakreslit jedním tahem. Ale jelikož může mít sudý počet hran ,tak nikdy nemohu konkrétně určit kolik mu nejvýše zbyde nebo ano ? poradí prosím někdo
✓ Téma bylo vyřešeno.
Marek T.
06. 12. 2015 02:16
1 odpověď
Tomáš B.
06.12.2015 02:16:24
Ahoj Marku, co to řešíš za úlohu, že musíš definice hledat na internetu a ne v učebnici?
- kolik komponent má eulerovský graf? jednu
- kolik komponent bude mít po odebrání první hrany? jednu (existuje uzavřená cesta délky alespoň dvě obsahující všechny hrany)
- kolik komponent bude mít po odebrání druhé hrany? jednu nebo dvě
Na bod (3) stačí najít příklad - každý uzavřený cyklus bude mít dvě komponenty po odebrání dvou hran.
Tím jsme dokázali dolní i horní hranici a je hotovo.
EDIT: Alternativně to může řešit takhle:
- v souvislém grafu s uzly sudého stupně neexistuje most, prvním odebráním tedy nelze vytvořit oddělené komponenty
- v uzavřeném cyklu lze vytvořit dvě komponenty odebráním dvou hran
Pro napsání komentáře se musíte přihlásit.