Średnica grafu niespójego i spójnego

matinf · Post autor: **matinf** » 10 maja 2014, o 17:09

Witam,

Jak to jest z tą średnicą takiego grafu. Powiedzmy, że mamy:
$\displaystyle{ f(x)=\min\(sr(G),sr( G'))}$
Przy czym średnicą grafu niespójnego uważamy za nieskończoność.
Graf z apostrofem to dopełnienie.

Jak znaleźć supremum tej fcji ?

Kartezjusz · Post autor: **Kartezjusz** » 10 maja 2014, o 17:16

średnica grafu wiesz co to jest, to zdefiniować?

matinf · Post autor: **matinf** » 10 maja 2014, o 17:41

Wiem:
Jest to minimum z odległości miedzy wszystkim parami wierzchołków. Zwracam uwagę na słowo odległości - tzn jeśli pomiędzy dwoma wierzchołkami są dwie ścieżki, to "liczy się" ta krótsza.

Kartezjusz · Post autor: **Kartezjusz** » 10 maja 2014, o 17:48

Rozważ na dzień dobry graf pełny i zauważ,że dopełnienie grafu lub sam graf są spójne. czyli funkcja jest ograniczona.

norwimaj · Post autor: **norwimaj** » 11 maja 2014, o 00:05

matinf pisze: $\displaystyle{ f(x)=\min\(sr(G),sr( G'))}$

Po lewej stronie nie ma $\displaystyle{ G}$, a po prawej nie ma $\displaystyle{ x}$. Poza tym warto by było napisać, jaka jest dziedzina tej funkcji. Zbiór wszystkich grafów?

Kartezjusz pisze:Rozważ na dzień dobry graf pełny i zauważ,że dopełnienie grafu lub sam graf są spójne. czyli funkcja jest ograniczona.

Przez co ta funkcja jest ograniczona? Przez $\displaystyle{ 3}$?

Kartezjusz · Post autor: **Kartezjusz** » 11 maja 2014, o 13:28

Rozważmy wszystkie podgrafy danego grafu; zbiór $\displaystyle{ \mathcal{G}}$ i z niego bierzemy argumenty

norwimaj · Post autor: **norwimaj** » 11 maja 2014, o 14:27

Ja myślę, że raczej chodziło o wszystkie grafy, a nie tylko o podgrafy danego grafu, ale niech będzie. Niech $\displaystyle{ G}$ będzie grafem pełnym na zbiorze $\displaystyle{ P(\NN)}$. Na jakiej podstawie twierdzisz, że dla dowolnego podgrafu grafu $\displaystyle{ G}$ wartość funkcji $\displaystyle{ f}$ jest równa co najwyżej $\displaystyle{ M}$, gdzie $\displaystyle{ M\in\RR}$ jest ustaloną liczbą? Twój powyższy argument nie jest dla mnie przekonujący. Ja bym raczej założył, że dla pewnego grafu wartość funkcji jest większa od $\displaystyle{ 3}$ i próbowałbym uzyskać sprzeczność.

Kartezjusz · Post autor: **Kartezjusz** » 11 maja 2014, o 14:34

Rozważamy grafy skończone. Przy nieskończonych wystarczy wziąć graf o wierzchołkach w $\displaystyle{ \mathbb{Q}^{2}}$ bez krawędzi, jako podgraf grafu na zbiorze liczb algebraicznych. Tutaj,rzeczywiście minimum to nieskończoność.

norwimaj · Post autor: **norwimaj** » 11 maja 2014, o 15:01

Kartezjusz pisze:Rozważamy grafy skończone.

Przypuszczam, że Matinf dostał to zadanie na swoich studiach, gdzie poziom matematyki dyskretnej jest bardzo wysoki. Nie wiem, czy może on po prostu przyjść na uczelnię i powiedzieć: "było za trudne i nie potrafiłem zrobić, ale w zamian za to rozwiązałem zadanie z przedszkola".

Kartezjusz pisze:Przy nieskończonych wystarczy wziąć graf o wierzchołkach w $\displaystyle{ \mathbb{Q}^{2}}$ bez krawędzi, jako podgraf grafu na zbiorze liczb algebraicznych. Tutaj,rzeczywiście minimum to nieskończoność.

Jeśli wziąłeś graf bez krawędzi, to jego dopełnienie jest kliką i ma średnicę (co najwyżej) $\displaystyle{ 1}$. Do nieskończoności jeszcze daleko.

Kartezjusz · Post autor: **Kartezjusz** » 11 maja 2014, o 15:24

Ale to nie jest spójne.

norwimaj · Post autor: **norwimaj** » 11 maja 2014, o 15:38

Kartezjusz pisze:Ale to nie jest spójne.

Co nie jest spójne?

Załóżmy, źe mamy graf $\displaystyle{ G}$ taki, że średnica $\displaystyle{ G}$ jest równa co najmniej $\displaystyle{ 4}$ i średnica $\displaystyle{ G'}$ też jest równa co najmniej $\displaystyle{ 4}$. W szczególności $\displaystyle{ G}$ i $\displaystyle{ G'}$ są spójne, bo jeśli graf nie jest spójny, to jego dopełnienie ma średnicę co najwyżej $\displaystyle{ 2}$. Weźmy wierzchołki $\displaystyle{ v_0,\ldots,v_9}$ takie, że $\displaystyle{ (v_0,\ldots,v_4)}$ jest najkrótszą ścieżką w $\displaystyle{ G}$, łączącą $\displaystyle{ v_0}$ i $\displaystyle{ v_4}$, oraz $\displaystyle{ (v_5,\ldots, v_9)}$ jest analogiczną ścieżką w $\displaystyle{ G'}$.

$\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(1,0){120}}
{\blue\put(0,40){\line(1,0){120}}}
\multiput(0,0)(30,0){5}{\circle*{3}}
\multiput(0,40)(30,0){5}{\circle*{3}}
\put(-3,-10){$0$}
\put(27,-10){$1$}
\put(57,-10){$2$}
\put(87,-10){$3$}
\put(117,-10){$4$}
\put(-3,44){$5$}
\put(27,44){$6$}
\put(57,44){$7$}
\put(87,44){$8$}
\put(117,44){$9$}
\end{picture}}$

Czarne kreski na rysunku oznaczają krawędzie w $\displaystyle{ G}$, a niebieskie w $\displaystyle{ G'}$. Brak krawędzi na rysunku oznacza, że nie wiadomo, w którym grafie ona jest.

Gdyby $\displaystyle{ (v_0, v_9)}$ i $\displaystyle{ (v_9,v_4)}$ należały do $\displaystyle{ G}$, tobyśmy sobie mogli skrócić drogę z $\displaystyle{ v_0}$ do $\displaystyle{ v_4}$ w $\displaystyle{ G}$, wbrew założeniu. Zatem któraś z tych krawędzi jest w $\displaystyle{ G'}$, bez straty ogólności $\displaystyle{ (v_0,v_9)\in G'}$.

$\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(1,0){120}}
{\blue\put(0,40){\line(1,0){120}}
\put(0,0){\line(3,1){120}}}
\multiput(0,0)(30,0){5}{\circle*{3}}
\multiput(0,40)(30,0){5}{\circle*{3}}
\put(-3,-10){$0$}
\put(27,-10){$1$}
\put(57,-10){$2$}
\put(87,-10){$3$}
\put(117,-10){$4$}
\put(-3,44){$5$}
\put(27,44){$6$}
\put(57,44){$7$}
\put(87,44){$8$}
\put(117,44){$9$}
\end{picture}}$

Teraz skoro w $\displaystyle{ G'}$ nie można sobie skrócić drogi z $\displaystyle{ v_5}$ do $\displaystyle{ v_9}$ przez $\displaystyle{ v_0}$, to $\displaystyle{ (v_5,v_0)\in G}$.

$\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(1,0){120}}
\put(0,0){\line(0,1){40}}
{\blue\put(0,40){\line(1,0){120}}
\put(0,0){\line(3,1){120}}}
\multiput(0,0)(30,0){5}{\circle*{3}}
\multiput(0,40)(30,0){5}{\circle*{3}}
\put(-3,-10){$0$}
\put(27,-10){$1$}
\put(57,-10){$2$}
\put(87,-10){$3$}
\put(117,-10){$4$}
\put(-3,44){$5$}
\put(27,44){$6$}
\put(57,44){$7$}
\put(87,44){$8$}
\put(117,44){$9$}
\end{picture}}$

Radź sobie dalej Matinfie. Powodzenia!-- 11 maja 2014, o 15:21 --Ale dziedzinę funkcji i tak doprecyzuj, bo to co ja sugerowałem, to oczywista bzdura. Zbiór wszystkich grafów nie istnieje, więc nie może być dziedziną funkcji.