Promień grafu.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
h2822
Użytkownik
Użytkownik
Posty: 35
Rejestracja: 31 paź 2020, o 17:43
Płeć: Mężczyzna
wiek: 20
Podziękował: 31 razy

Promień grafu.

Post autor: h2822 »

Mam spory problem z dwoma zadaniami, które na pierwszy rzut oka wydają się proste.
1. Wykaż, że w grafie spójnym \(\displaystyle{ G:\quad \text{rad}{G} \leq \frac{|G|}{2} }\)
2. Wykaż, że w grafie dwudzielnym spójnym \(\displaystyle{ G=\left(X,Y;E\right)}\), gdzie \(\displaystyle{ |X|<|Y|:\quad \text{rad}{G} \leq |X|}\)
Próbowałem do dowodów podchodzić nie wprost, indukcyjnie, ale jakkolwiek bym tego nie tknął, nie wiem jak to dociągnać do końca, co jest o tyle frustrujące, że same tezy wydaję się dosyć oczywiste. Byłbym bardzo wdzięczny za wszelką pomoc.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Promień grafu.

Post autor: Dasio11 »

1. Rozważmy najdłuższą ścieżkę \(\displaystyle{ \gamma}\) w grafie \(\displaystyle{ G}\). Załóżmy, że ma ona długość parzystą \(\displaystyle{ 2n}\), i niech \(\displaystyle{ w}\) będzie jej środkiem. Mamy oczywiście \(\displaystyle{ 2n \le |G|-1}\), pozostaje więc wykazać, że \(\displaystyle{ d(u, w) \le n}\) dla każdego wierzchołka \(\displaystyle{ u}\).

Weźmy dowolny wierzchołek \(\displaystyle{ u}\) i niech \(\displaystyle{ v}\) będzie wierzchołkiem \(\displaystyle{ \gamma}\) leżącym najbliżej \(\displaystyle{ u}\). Ten wierzchołek dzieli połowę ścieżki \(\displaystyle{ \gamma}\) na dwie części: \(\displaystyle{ \gamma_1}\) idącą od \(\displaystyle{ w}\) do \(\displaystyle{ v}\) i \(\displaystyle{ \gamma_2}\) idącą od \(\displaystyle{ v}\) do końca. Oczywiście mamy wtedy \(\displaystyle{ d(v, w) \le \ell(\gamma_1)}\). Mamy też \(\displaystyle{ d(u, v) \le \ell(\gamma_2)}\), bo w przeciwnym razie można by zastąpić \(\displaystyle{ \gamma_2}\) najkrótszą ścieżką od \(\displaystyle{ v}\) do \(\displaystyle{ u}\) otrzymując ścieżkę dłuższą niż \(\displaystyle{ \gamma}\). Stąd \(\displaystyle{ d(u, w) \le d(u, v) + d(v, w) \le \ell(\gamma_1) + \ell(\gamma_2) = n}\).

Jeśli \(\displaystyle{ \gamma}\) ma długość nieparzystą, rozumujemy podobnie, poczynając od wzięcia wierzchołka \(\displaystyle{ w}\) dzielącego \(\displaystyle{ \gamma}\) na ścieżki długości \(\displaystyle{ n}\) i \(\displaystyle{ n+1}\).
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Promień grafu.

Post autor: kerajs »

1. Zakładam, możliwe że błędnie, iż \(\displaystyle{ |G| }\) to liczba wierzchołków grafu G.
Graf liniowy o \(\displaystyle{ |G| }\) wierzchołkach ma promień równy \(\displaystyle{ \frac{|G|}{2} }\) dla parzystego \(\displaystyle{ |G| }\) lub \(\displaystyle{ \frac{|G|-1}{2} }\) dla nieparzystego \(\displaystyle{ |G| }\).
Dodawanie do niego kolejnych krawędzi może powodować zmniejszanie acentryczności niektórych lub wszystkich wierzchołków grafu, więc i zmniejszenie promienia grafu.

2. Największy możliwy graf liniowy wydzielony z G ma \(\displaystyle{ 2|X|+1}\) wierzchołków więc jego promień (patrz zadanie 1. ) to: \(\displaystyle{ \frac{(2|X|+1)-1}{2}=|X| }\)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Promień grafu.

Post autor: Dasio11 »

kerajs pisze: 25 kwie 2022, o 10:531.
Graf liniowy o \(\displaystyle{ |G| }\) wierzchołkach ma promień równy \(\displaystyle{ \frac{|G|}{2} }\) dla parzystego \(\displaystyle{ |G| }\) lub \(\displaystyle{ \frac{|G|-1}{2} }\) dla nieparzystego \(\displaystyle{ |G| }\).
Dodawanie do niego kolejnych krawędzi może powodować zmniejszanie acentryczności niektórych lub wszystkich wierzchołków grafu, więc i zmniejszenie promienia grafu.
W jaki sposób wynika stąd teza zadania?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Promień grafu.

Post autor: kerajs »

W każdym grafie spójnym są podgrafy liniowe. W najlepszym razie istnieje podgraf liniowy o wszystkich wierzchołkach grafu.
kerajs pisze: 25 kwie 2022, o 10:53 Graf liniowy o \(\displaystyle{ |G| }\) wierzchołkach ma promień równy \(\displaystyle{ \frac{|G|}{2} }\) dla parzystego \(\displaystyle{ |G| }\) lub \(\displaystyle{ \frac{|G|-1}{2} }\) dla nieparzystego \(\displaystyle{ |G| }\).
Dodawanie do niego kolejnych krawędzi może powodować zmniejszanie acentryczności niektórych lub wszystkich wierzchołków grafu, więc i zmniejszenie promienia grafu.
Jeśli najdłuższy podgraf liniowy ma mniej wierzchołków, to jego promień nie może być większy od wskazanych powyżej, więc i graf nie może mieć większego promienia.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Promień grafu.

Post autor: Dasio11 »

Cały czas zdajesz się powoływać na nietrywialny lemat: "promień grafu jest nie większy niż promień jego najdłuższego podgrafu liniowego" w zasadzie będący istotą zadania.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Promień grafu.

Post autor: kerajs »

Niczego takiego nie robię.

Przejście do grafu od jego podgrafu liniowego jest tu:
kerajs pisze: 25 kwie 2022, o 10:53 Dodawanie do niego kolejnych krawędzi może powodować zmniejszanie acentryczności niektórych lub wszystkich wierzchołków grafu, więc i zmniejszenie promienia grafu.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Promień grafu.

Post autor: Dasio11 »

Jeśli dobrze rozumiem, szkic Twojego dowodu jest taki:
Weźmy najdłuższy liniowy podgraf \(\displaystyle{ G}\). Ma on nie więcej wierzchołków niż \(\displaystyle{ |G|}\), zatem jego promień jest nie większy niż \(\displaystyle{ \frac{|G|}{2}}\). Dodając do niego pozostałe krawędzie grafu \(\displaystyle{ G}\) nie zwiększamy jego promienia, a zatem i cały graf \(\displaystyle{ G}\) ma promień spełniający żądaną nierówność.
W takim wypadku błąd jest w założeniu, że każdy graf powstaje ze swojego najdłuższego podgrafu liniowego przez dodawanie samych krawędzi, co jest prawdą tylko dla grafów mających ścieżkę Hamiltona.

Jeśli zaś nie rozumiem i szkic jest inny, to proponuję byś zapisał go od początku do końca.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Promień grafu.

Post autor: kerajs »

Dasio11 pisze: 26 kwie 2022, o 10:49 W takim wypadku błąd jest w założeniu, że każdy graf powstaje ze swojego najdłuższego podgrafu liniowego przez dodawanie samych krawędzi, co jest prawdą tylko dla grafów mających ścieżkę Hamiltona.
Bynajmniej. O grafach których nie można uzyskać z najdłuższego podgrafu liniowego przez dodawanie samych krawędzi piszę tu:
kerajs pisze: 25 kwie 2022, o 14:50 Jeśli najdłuższy podgraf liniowy ma mniej wierzchołków, to jego promień nie może być większy od wskazanych powyżej, więc i graf nie może mieć większego promienia.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Promień grafu.

Post autor: Dasio11 »

Powtórzę więc prośbę o uzasadnienie kluczowego przejścia:
kerajs pisze: 25 kwie 2022, o 14:50promień [najdłuższego podgrafu liniowego] nie może być większy od wskazanych powyżej, więc i graf nie może mieć większego promienia.
dla wszystkich grafów (w tym tych niemających ścieżki Hamiltona), skoro już zgadzamy się co do tego, że Twoje poprzednie uzasadnienie:
kerajs pisze: 26 kwie 2022, o 08:15 Przejście do grafu od jego podgrafu liniowego jest tu:
kerajs pisze: 25 kwie 2022, o 10:53 Dodawanie do niego kolejnych krawędzi może powodować zmniejszanie acentryczności niektórych lub wszystkich wierzchołków grafu, więc i zmniejszenie promienia grafu.
działa tylko dla grafów ze ścieżką Hamiltona.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Promień grafu.

Post autor: kerajs »

Dasio11 pisze: 30 kwie 2022, o 08:52 skoro już zgadzamy się co do tego, że Twoje poprzednie uzasadnienie(...)
działa tylko dla grafów ze ścieżką Hamiltona.
Ani się z tym nie zgadzam, ani nic takiego nie napisałem.

Mimo to wnoszę, że uzasadnienie dla grafów w których najdłuższy podgraf liniowy zawiera wszystkie wierzchołki grafu jest zrozumiałe (skoro droga między wierzchołkami stopnia 1 jest ścieżką (lub jedną ze ścieżek) Hamiltona).

Teraz to, czego nie rozumiesz:
1. Jeśli najdłuższy podgraf liniowy ma mniej wierzchołków niż \(\displaystyle{ |G|}\), to promień tego grafu liniowego jest niewiększy (a zwykle mniejszy) niż promień grafu liniowego o \(\displaystyle{ |G|}\) wierzchołkach.
2. Dołączanie do najdłuższego podgrafu liniowego gałęzi z pozostałymi wierzchołkami nie spowoduje zwiększenie promienia. Gdyby tak się działo, to oznaczałoby to, iż wybrany najdłuższy podgraf faktycznie najdłuższym nie był.
3. Dołączanie pozostałych krawędzi nie powoduje zwiększenia promienia.

Który z podpunktów jest niezrozumiały?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Promień grafu.

Post autor: Dasio11 »

kerajs pisze: 2 maja 2022, o 09:34Ani się z tym nie zgadzam, ani nic takiego nie napisałem.
Ja naszą dyskusję widzę tak:

D: Żeby przejście X działało, potrzebujesz nietrywialnego lematu.
K: Nie potrzebuję, uzasadniam go w Y.
D: Ale Y działa tylko dla grafów ze ścieżką Hamiltona.
K: O grafach bez ścieżki Hamiltona piszę tu: X.


Nie tylko więc w dalszym ciągu nie uzasadniłeś przejścia X, ale i trudno mi było nie odnieść wrażenia że uznajesz moje zastrzeżenie dotyczące argumentu Y, skoro zamiast mu zaprzeczyć powołujesz się na inny argument (a ściślej mówiąc, na tezę).

kerajs pisze: 2 maja 2022, o 09:34Teraz to, czego nie rozumiesz:
[...]
2. Dołączanie do najdłuższego podgrafu liniowego gałęzi z pozostałymi wierzchołkami nie spowoduje zwiększenie promienia. [...]
3. Dołączanie pozostałych krawędzi nie powoduje zwiększenia promienia.
Trzeba niemałej bezczelności, by po tym gdy w dyskusji zostanie wytknięta niepoprawność jakiegoś argumentu, po cichu poprawić ten argument (a nuż nikt się nie zorientuje?) i twierdzić, że to inni czegoś nie rozumieją.

Od samego początku piszesz o tym, że cały graf ma powstać ze swojego podgrafu liniowego przez dodawanie krawędzi:
kerajs pisze: 25 kwie 2022, o 10:53Graf liniowy o \(\displaystyle{ |G| }\) wierzchołkach ma promień równy [...]
Dodawanie do niego kolejnych krawędzi może powodować [...] zmniejszenie promienia grafu.
Teraz zaś - gdy jak rozumiem wreszcie dotarło do Ciebie, że napisałeś coś innego niż miałeś na myśli - zamiast otwarcie przyznać się do pomyłki, wolałeś sparafrazować argument tak by wyglądało, że żadnego błędu nie było.

I wreszcie: nadal brakuje uzasadnienia kluczowego przejścia, że dodawanie do najdłuższego podgrafu liniowego pozostałych "gałęzi" nie zwiększy jego promienia (przejście "X"). Jedyna jak dotychczas próba:
kerajs pisze: 2 maja 2022, o 09:34Gdyby tak się działo, to oznaczałoby to, iż wybrany najdłuższy podgraf faktycznie najdłuższym nie był.
jest w zasadzie powtórzeniem tezy, a nie argumentem.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Promień grafu.

Post autor: kerajs »

Widzę, że nieźle odpłynąłeś wypisując powyższe argumenta.

Mimo to proponuję prostą rzecz. Wskaż graf, a ja na nim pokażę jak działa to, co napisałem.
ODPOWIEDZ