Strona 1 z 1

Centrum w drzewie

: 1 lip 2022, o 19:53
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 ?

Re: Centrum w drzewie

: 19 lip 2022, o 14:44
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, ...