Witam,
Czy ktoś może pomóc w rozwiązaniu poniższych zadań?
1.Czy w każdym grafie spójnym można wyznaczyć taką drogę by każdej krawędzi przejść dokładnie dwa razy?
2.Jeżeli graf \(\displaystyle{ G}\) jest spójny to pokaż, że z \(\displaystyle{ G}\) można usunąć wierzchołek, tak aby \(\displaystyle{ G}\) wciąż był spójny
3. Graf \(\displaystyle{ K_{m,n}}\) jaki warunek muszą spełniać \(\displaystyle{ m}\) i \(\displaystyle{ n}\), aby graf był Hamiltonowski?
Z góry piękne dzięki!:)
Grafy
Grafy
Ostatnio zmieniony 1 lut 2020, o 15:13 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Grafy
Hm, to chyba za dużo nie pomogę. Moje pomysły bazowałyby na tym, że graf spójny można budować dodając wierzchołek (z krawędzią) lub samą krawędź i startując od jednego punktu. Można tak robić na pewno jak jest graf skończony, ale nie wiem, czy to jest prawda w ogólności (nie miałem teorii grafów za dużo na studiach). A co oznacza \(\displaystyle{ K(n,m)}\)?