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?
Grafy pełne
-
- 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
Znalezienie cyklów Hamiltona w tych grafach jest zadaniem trywialnym.Sugre pisze:Tylko trudno jest mi sprawdzić czy są one hamiltonowskie, może ktoś wie?
-
- 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
Aha, no fakt. Pomyliłem twierdzenia. Jeden i drugi jest
A jakbyśmy je skleili wspólną krawędzią, to też by były?
A jakbyśmy je skleili wspólną krawędzią, to też by były?
-
- 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
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.
-
- 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
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.