Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Ahoj,
Příklad zní.
Je-li graf hranově tranzitiví a zároveň není vrcholově tranzitivní, pak je bipartitní.
Dokaž.
Umím to dokázat pro případ, kdy graf nemá vrchol stupně nula.
Můj důkaz:
Je , jinak by byl graf triviálně vrcholově tranzitivní.
Volme . To udělat mohu, protože kdyby , pak by všechny vrcholy měly nulový stupeň a navíc by byl graf vrcholově tranzitivní.
Označme:
,
,
kde .
Chci ukázat, že tyto (neprázdné) množiny jsou disjunktním rozkladem :
Graf je vrcholově tranzitivní, proto je .
Kdyby , pak volím .
Chci ukázat, že tento předpoklad vede ke sporu s tím, že není vrcholově tranzitivní.
Pro libovolné dva vrcholy platí - jsou buďto oba v jedné z dvou množin , pak ale existuje automorfismus, který zobrazuje BÚNO a jiný, . Pak a je to automorfismus.
Pokud jsou naopak oba vrcholy v jiné z dvou množin, je BÚNO
, , ale mame a , odkud je automorfismus , který zobrazuje na .
je vrcholově tranzitivní, což je spor s předpokladem, že není. Musí tedy být , a je tedy bipartitní.
Jak to mám udělat, pokud existuje vrchol nenulového stupně? Nebo pak tvrzení neplatí?
Díky,
A.
PS: definice: graf
Offline
Myslím, že mám protipříklad:
Graf s vrcholy , kde vrcholy 1,2,3 tvoří kružnici a vrchol 4 má nulový stupeň. Takový graf je hranově tranzitivní, není vrcholově tranzitivní a není bipartitní.
Offline
Stránky: 1