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: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Centrum w drzewie

Post autor: mol_ksiazkowy »

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: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

Re: Centrum w drzewie

Post autor: 3a174ad9764fefcb »

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