Matematické Fórum

etchie · 07. 01. 2013 18:08

Ahojte,

nutná a postačujúca podmienka pre acyklickosť orientovaného grafu je:

nech $\vec{G}(V,H)$ je orientovaný graf
ak existuje postupnosť $1,2,.....|V|$ taká, že každému vrcholu grafu priradím práve jedno číslo z tejto postupnosti, tak aby platilo $\forall h(i,j): i<j; h \in H$ potom je tento digraf acyklický.

Akým spôsobom je možné dokázať túto podmienku ?
Mňa napadlo niečo také ako, predpokladať, že takto označený digraf je cyklický. To znamená že posledný vrchol "necyklu" je spojený s prvým a teda malo by platiť $v_0 > v_{|V|}$ , čo je ale spor s pôvodným tvrdením $i<j$ a teda platí pôvodné tvrdenie. Príde mi to ale príliš triviálne ako dôkaz.

Ďakujem

etchie · 08. 01. 2013 09:52

↑ etchie:

keďže nikto nereaguje, mám to chápať tak, že uvedený dôkaz je dostatočný a niet čo riešiť ?

Matematické Fórum

#1 07. 01. 2013 18:08

dôkaz pre acyklický orientovaný graf

#2 08. 01. 2013 09:52

Re: dôkaz pre acyklický orientovaný graf

Zápatí