Matematické Fórum

E@sy · 24. 01. 2011 07:56

Dobrý den,
mám obecně problém s důkazy, jak správně formulovat a podobně, mohl by mi někdo mopoci dokázat tyto dvě tvrzení?

1) (dokázat sporem) G je strom, pak mezi každými dvěma vrcholy grafu G existuje právě jedna cesta
z definice stromu přímo plyne toto tvrzení... co mě napadlo jít na to s předpokladem, že tam existuje kružnice, v tom případě by existovalo více cest a to by byl spor s tím, že jde o strom neboť strom neobsahuje kružnici.... ale jak to spravně formulovat?

2) (vyvrátit spoprem) v grafu G neexistuje most, pak G má všechny vrcholy stupně sudého
je mi jasné, že mostem může být pouze stromová hrana (prohledávání do hloubky), ale vrchol stromové hrany může být klidně stupně 1 nebo napak i více než dvě. (Napadlo mě ještě využít principu sudosti)

prosím o radu, respektive spravnou formulaci těchto dvou problémů

kosto · 24. 01. 2011 08:46

Možno takto:

1. Nech G je strom. Z definície stromu vyplýva, že G je súvislý, preto medzi každými dvoma vrcholmi existuje aspoň jedna cesta. Treba dokázať, že práve jedna.

Za účelom sporu teda predpokladajme, že v grafe existuje dvojica vrcholov $u,v \in V(G)$ , ktoré sú spojené aspoň dvoma rôznymi u-v-cestami. Označme tieto cesty $P_1$ a $P_2$ . Označme $w_1$ vrchol na ceste $P_1$ taký, že až do vrchola $w_1$ sú cesty $P_1$ a $P_2$ zhodné ( $w_1$ teda leží aj na $P_2$ ), ale za vrcholom $w_1$ obe cesty pokračujú rôznymi hranami - z predpokladu rôznosti ciest vyplýva, že takýto vrchol musí existovať. Označme $w_2$ prvý vrchol na ceste $P_1$ , ktorý je za $w_1$ a súčasne leží aj na ceste $P_2$ (t.j. prvý vrchol za $w_1$ , kde sa cesty $P_1$ a $P_2$ opäť zídu). Takýto vrchol tiež musí existovať, keďže obe cesty končia v rovnakom vrchole. Úseky ciest $P_1[w_1,w_2]$ a $P_2[w_1,w_2]$ sú zrejme až na počiatočný a koncový vrchol vrcholovo disjunktné - ináč by sme dostali spor s voľbou $w_2$ . Z toho vyplýva, že $P_1[w_1,w_2] P_2^{-1}[w_1,w_2]$ (ak C je u-v-cesta, tak symbolom $C^{-1}$ označujem obrátenú cestu z v do u) je kružnica v G, čo je spor s predpokladom, že $G$ je strom.

2. Pri takýchto úlohách stačí uviesť kontrapríklad. Stačí vziať napríklad $K_4$ . Dokázať o tomto grafe, že nemá most je ľahké (napríklad sa dá ukázať, že každá hrana leží na kružnici, čo je s tým ekvivalentné; alebo to možno spraviť drevorubačským prejdením všetkých hrán, pričom o každej ukážeme, že nie je most). Rovnako je zrejmé, že každý vrchol je stupňa 3. To znamená, že uvedená implikácia nemusí nutne platiť.

E@sy · 24. 01. 2011 10:45

↑ kosto:

2) v grafu G neexistuje most, pak G má všechny vrcholy stupně sudého.

Nechť existuje graf K, kde všechny jeho vrcholy budou stupně 3 (K4) a každý vrchol je spojen hranou s ostatními vrcholy. Mějme cestu Pvw, která je tvořena hranou e=(v,w), kde v a w jsou libovolné dva vrcholy grafu K4. Pokud odebereme hranu e, musí existovat jiná cesta Pvw, což je dáno vlastností, že každý vrchol je spojen se všemi ostatními hranou. Existuje tedy cesta Pvxw.

předpokládám, že ale nejde o zcela korektní důkaz, můžete mi prosím poradit, jak jej zformulovat správně?

kosto · 24. 01. 2011 14:33

↑ E@sy:

Podľa mňa je ten dôkaz dobrý. Ja by som to napísal asi nejako takto: uvažujme kompletný graf $K_4$ (každý vrchol v ňom má nepárny stupeň). Chceme dokázať, že nemá most. Predpokladajme teda, že existuje dvojica vrcholov $v_1,v_2 \in V(K_4)$ tak, že hrana $v_1 v_2$ je most. To znamená, že po odobratí hrany $v_1 v_2$ sa nám graf rozpadne na dva komponenty súvislosti, pričom $v_1$ leží v jednom, $v_2$ v druhom. Ale $K_4$ obsahuje štyri vrcholy, čo znamená, že existuje,vrchol $v_3$ rôzny od $v_1$ a $v_2$ . Z kompletnosti grafu vyplýva, že v grafe existujú hrany $v_1 v_3$ ako aj $v_2 v_3$ . To znamená, že v grafe $K_4 - \{v_1 v_2\}$ máme cestu $v_1 v_3 v_2$ , čo je spor s tým, že $v_1$ a $v_2$ ležia v rôznych komponentoch súvislosti.