Średnica i obwód grafu - matma dyskretna

[hutsalo]

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]

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ą.

[hutsalo]

A mółgłbym prosić o przykład jak do tego doszedłeś

[kerajs]

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).