Centrum w drzewie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 8528
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2759 razy
Pomógł: 703 razy

Centrum w drzewie

Post autor: mol_ksiazkowy » 1 lip 2022, o 19:53

W drzewie jest tylko jedno bądź dwa centra. Czy w takim przypadku są one zawsze połączone krawędzią ? A jak będzie dla innych grafów o dwóch centrach ?
Czy istnieją grafy o trzech bądź więcej centrach ?

3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 99
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 34
Podziękował: 2 razy
Pomógł: 7 razy

Re: Centrum w drzewie

Post autor: 3a174ad9764fefcb » 19 lip 2022, o 14:44

1) Jeśli \(\displaystyle{ v_0}\) jest centrum i największa odległość \(\displaystyle{ v_0}\) od innego wierzchołka w drzewie jest równa \(\displaystyle{ d}\),to istnieje ścieżka złożona z \(\displaystyle{ d}\) różnych wierzchołków: \(\displaystyle{ v_0v_1\ldots v_{d}}\). Ponadto można ją przedłużyć do \(\displaystyle{ 2d}\) wierzchołków: \(\displaystyle{ v_{d-1}\ldots v_{-1}v_0v_1\ldots v_{d}}\), bo inaczej wierzchołek \(\displaystyle{ v_1}\) byłby odległy o co najwyżej \(\displaystyle{ d-1}\) od każdego innego, więc \(\displaystyle{ v_0}\) nie byłby centrum. Ostatecznie żaden wierzchołek w drzewie oprócz \(\displaystyle{ v_0}\) i \(\displaystyle{ v_1}\) nie może być centrum, bo jest odległy o więcej niż \(\displaystyle{ d}\) od \(\displaystyle{ v_{d-1}}\) albo od \(\displaystyle{ v_d}\).

2) Graf o sześciu wierzchołkach: kwadrat z dwiema antenkami na przeciwległych wierzchołkach.

3) Cykle, kliki, ...

ODPOWIEDZ