Promień grafu.
-
- Użytkownik
- Posty: 35
- Rejestracja: 31 paź 2020, o 17:43
- Płeć: Mężczyzna
- wiek: 20
- Podziękował: 31 razy
Promień grafu.
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.
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.
- Dasio11
- 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.
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}\).
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}\).
- kerajs
- 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.
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| }\)
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| }\)
- Dasio11
- 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.
W jaki sposób wynika stąd teza zadania?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.
- kerajs
- 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.
W każdym grafie spójnym są podgrafy liniowe. W najlepszym razie istnieje podgraf liniowy o wszystkich wierzchołkach 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.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.
- Dasio11
- 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.
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.
- kerajs
- 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.
Niczego takiego nie robię.
Przejście do grafu od jego podgrafu liniowego jest tu:
Przejście do grafu od jego podgrafu liniowego jest tu:
- Dasio11
- 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.
Jeśli dobrze rozumiem, szkic Twojego dowodu jest taki:
Jeśli zaś nie rozumiem i szkic jest inny, to proponuję byś zapisał go od początku do końca.
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.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ść.
Jeśli zaś nie rozumiem i szkic jest inny, to proponuję byś zapisał go od początku do końca.
- kerajs
- 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.
Bynajmniej. O grafach których nie można uzyskać z najdłuższego podgrafu liniowego przez dodawanie samych krawędzi piszę tu:
- Dasio11
- 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.
Powtórzę więc prośbę o uzasadnienie kluczowego przejścia:
dla wszystkich grafów (w tym tych niemających ścieżki Hamiltona), skoro już zgadzamy się co do tego, że Twoje poprzednie uzasadnienie:
działa tylko dla grafów ze ścieżką Hamiltona.
- kerajs
- 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.
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?
- Dasio11
- 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.
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ę).
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:
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:
jest w zasadzie powtórzeniem tezy, a nie argumentem.