Grafy pełne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Sugre
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 1 paź 2011, o 18:34
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Grafy pełne

Post autor: Sugre »

Mam takie dwa zadania i potrzebowałbym waszej pomocy:

1. Czy grafy pełne \(\displaystyle{ K _{6}}\) i \(\displaystyle{ K _{7}}\) są Eulerowskie? A hamiltonowskie?

To że \(\displaystyle{ K _{6}}\) nie jest Eulerowski, a \(\displaystyle{ K _{7}}\) jest, to wiem. Tylko trudno jest mi sprawdzić czy są one hamiltonowskie, może ktoś wie? mam tylko napisać TAK lub NIE.

2. Ile jest nieizoformicznych grafów, które mają 6 krawędzi i 5 wierzchołków?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Grafy pełne

Post autor: norwimaj »

Sugre pisze:Tylko trudno jest mi sprawdzić czy są one hamiltonowskie, może ktoś wie?
Znalezienie cyklów Hamiltona w tych grafach jest zadaniem trywialnym.
Sugre
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 1 paź 2011, o 18:34
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Grafy pełne

Post autor: Sugre »

Aha, no fakt. Pomyliłem twierdzenia. Jeden i drugi jest
A jakbyśmy je skleili wspólną krawędzią, to też by były?
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Grafy pełne

Post autor: norwimaj »

Jeśli końce sklejanej krawędzi oznaczymy przez \(\displaystyle{ x}\) i \(\displaystyle{ y}\), możesz pójść dowolną ścieżką Hamiltona z \(\displaystyle{ x}\) do \(\displaystyle{ y}\) w jednym grafie, a następnie ścieżką Hamiltona z \(\displaystyle{ y}\) do \(\displaystyle{ x}\) w drugim grafie.
Sugre
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 1 paź 2011, o 18:34
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Grafy pełne

Post autor: Sugre »

Dajesz mi do myślenia i z tego co mi napisałeś, to wnioskuje że wtedy nie będą.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Grafy pełne

Post autor: norwimaj »

Jak to? Nie odwiedziłeś każdego wierzchołka dokładnie raz?
Sugre
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 1 paź 2011, o 18:34
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Grafy pełne

Post autor: Sugre »

Zrozumiałem że przechodzimy dwukrotnie najpierw z \(\displaystyle{ x}\) do \(\displaystyle{ y}\), a później z \(\displaystyle{ y}\) do \(\displaystyle{ x}\). Tylko teraz wiem, że opisałeś drugi, osobny przypadek.
ODPOWIEDZ