Dotaz: co je necyklický graf?

[eliška]

prosím polopaticky, jsem blondýna :)

Odpovědi

[camel1cz]

Že by graf bez cyklů? Např. Strom. Je to už nějaký pátek, ale používali jsme tuším výraz acyklicky. Význam bude stejný

[Sten]

Necyklický/acyklický graf je graf, kde z libovolného bodu do libovolného jiného bodu vede právě jedna cesta.

[Jendа]

Nestačí nejvýše jedna cesta? Nesouvislý graf může být taky acyklický.

[Sten]

Pravda, na nesouvislé grafy jsem si vůbec nevzpomněl.

[AraxoN]

No a potom sú ešte orientované grafy (jednosmerné hrany) a tam takáto definícia cyklu zase nesedí.

[VM]

Necyklický graf je přece graf bez cyklu, tzn. bez kružnice ( u orientovaného grafu se myslí orientovaná kružnice). Takže mezi dvěma různými vrcholy nemůžu jít jednou cestou tam, a jinou zpět.

[Xerces]

Teď ještě blondýně elišce vysvětlete co je to ten cyklus, který vy zrovna máte na mysli.

[VN]

Pro blondýny - když můžu jít grafem tak, že aniž bych se vracel po stejné hraně, vrátím se do stejného uzlu, odkud jsem vyšel, tak jsem právě prošel kružnici. Pro blondýny, které to potřebují do školy (kam taky jinam) http://cs.wikipedia.org/wiki/Kru%C5%BEnice_(graf) Graf, který obsahuje kružnici, je cyklický.

[:::]

http://en.wikipedia.org/wiki/Directed_acyclic_graph