Matematické Fórum

Třeba "síť" jakéhokoliv polopravidelného mnohostěnu. http://en.wikipedia.org/wiki/Semiregular_polyhedron
(Síť teď nemyslím jako rozkreslení pláště do roviny, ale jako graf, v němž vrcholy a hrany grafu odpovídají vrcholům a hranám mnohostěnu.)

Nejmenší graf tak dostaneš jako síť trojbokého hranolu, tj. na 6 vrcholech. Menší příklad najít nelze.

No hranově tranzitivní znamená, že pokud vyberu dvě hrany, tak existuje automorfizmus, který převádí jednu na druhou. A to u trojbokého hranolu nefunguje -- vezmu-li hranu z jedné podstavy, tak nenajdu automorfizmus, který ji zobrazí na boční hranu (boční hrana neleží na kružnici délky 3).

↑ kajbl: To je přesně to, co jsem myslel. Definici hranové tranzitivity jsem našel zde: http://kam.mff.cuni.cz/~samal/vyuka/Toky/

↑ kajbl:Ano, graf na obrázku není ani VT ani HT.
Avšak s předchozím odstavcem o vrcholové a hranové tranzitiviě nemohu souhlasit.
Platí, že graf, který je VT, MUSÍ mít všechny vrcholy stejného stupně. Ale opačná implikace prostě neplatí. Najdeme spoustu grafů, které jsou pravidelné, ale nejsou vrcholově tranzitivní.
Hranově tranzitivní graf NEMUSÍ mít všechny vrcholy stejného stupně (třeba ). Samozřejmě HT graf musí celou řadu automorfismů. To vyplývá hned z definice HT grafu. Ale není pravda, ža pokud najdeme NĚJAKOU symetrii, tak už bude HT. Troufnu si tvrdit, že naopak většina grafů, které mají NĚJAKOU symetrii nejsou ani HT ani VT.

↑ kajbl:Ano, podle definice je potřeba prověřit každou dvojici hran, aby byl graf HT a každou dvojici vrcholů, aby byl VT.
Pěkné na tom je, že pokud graf je VT nebo HT, tak bude mít řadu automorfismů a bude stačit zkoušet jen některé dvojice, zbývající budou "jasné ze symetrie grafu".