Średnica i obwód grafu - matma dyskretna
-
- Użytkownik
- Posty: 142
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Średnica i obwód grafu - matma dyskretna
Wyznacz obwód i średnice grafów \(\displaystyle{ K_{3,3}, K_{5}, K_{4,4}, K_{6}}\). Ustal czy grafy te mają ścieżkę Eulera. Nie musi być to rozwiązane dla wszystkich przykładów, może być 1 ewentualnie 2.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Średnica i obwód grafu - matma dyskretna
Obwód dla klik to \(\displaystyle{ 3}\), a dla grafów dwudzielnych \(\displaystyle{ 4}\).
Średnica (i promień) dla klik to \(\displaystyle{ 1}\) , a dla grafów dwudzielnych \(\displaystyle{ 2}\).
Ścieżki Eulera nie mają grafy o nieparzystych stopniach wierzchołków, czyli \(\displaystyle{ K_6}\) i \(\displaystyle{ K_{3,3}}\), a pozostałe ją posiadają.
Średnica (i promień) dla klik to \(\displaystyle{ 1}\) , a dla grafów dwudzielnych \(\displaystyle{ 2}\).
Ścieżki Eulera nie mają grafy o nieparzystych stopniach wierzchołków, czyli \(\displaystyle{ K_6}\) i \(\displaystyle{ K_{3,3}}\), a pozostałe ją posiadają.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Średnica i obwód grafu - matma dyskretna
Obwód, średnica i promień wynikają ze swoich definicji . W klice najmniejsze cykle to trójkąty, najdłuższe drogi to 1, a acentryczności każdego z wierzchołków to też 1. W pełnych grafach dwudzielnych najmniejsze cykle to czworokąty, najdłuższe drogi mają dwie krawędzie, a acentryczność każdego z wierzchołków to 2.
Ścieżka Eulera może być w grafie o co najwyżej dwóch wierzchołkach nieparzystego stopnia, Wskazana klika ma sześć wierzchołków stopnia 5, a klika dwudzielna tyleż samo wierzchołków lecz stopnia 3. Pozostałe grafy mają cykl Eulera (co sprawdzisz je rysując).
Ścieżka Eulera może być w grafie o co najwyżej dwóch wierzchołkach nieparzystego stopnia, Wskazana klika ma sześć wierzchołków stopnia 5, a klika dwudzielna tyleż samo wierzchołków lecz stopnia 3. Pozostałe grafy mają cykl Eulera (co sprawdzisz je rysując).