Matematické Fórum

pizet · 30. 12. 2011 09:39

Ahojte, potreboval by som hint ako vyriešiť túto úlohu:

Definície.

Graf $G = (V,E)$ sa nazýva vrcholovo tranzitivný, ak pre ľubovoľné dva vrcholy $v,\ v^{'}\in V$ existuje automorfizmus $f\ :\ V\rightarrow V$ grafu $G$ taký, že $f(v) = v^{'}$ .
Graf $G = (V,E)$ sa nazýva hranovo tranzitivný, ak pre ľubovoľné dve hrany $\{u,v\},\{u^{'},v^{'}\}\in E$ existuje automorfizmus $f\ :\ V\rightarrow V$ grafu $G$ taký, že $\{f(u),f(v)\} = \{u^{'},v^{'}\}$ .

Úloha.

Dokážte, že graf, ktorý je hranovo tranzitivný a nie je vrcholovo tranzitivný je nutne bipartitný.

Za pomoc ďakujem.

Matematické Fórum

#1 30. 12. 2011 09:39

Grafy - vrcholová a hranová trazitivita

Zápatí