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 ?
Centrum w drzewie
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
-
- 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
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, ...
2) Graf o sześciu wierzchołkach: kwadrat z dwiema antenkami na przeciwległych wierzchołkach.
3) Cykle, kliki, ...