Inne, zadanie nr 1152

Autor	Zadanie / Rozwiązanie
sebastian123 postów: 22	2013-02-28 12:26:49 Witam, studiuje informatyke i na przyszly kolos mają być grafy. Prosiłbym tylko o wyjaśnienie dwóch przykładów: 1).Jeśli w implementacji przez macierz sąsiedztwa graf nie skierowany G wygląda następująco: 1 2 3 4 1:0 1 0 1 2:0 0 1 0 3:0 1 0 1 4:0 1 0 0 to w G istnieje cykl a) 1,2,3,1 b) 2,3,4,2 c) 3,4,1,3 d) 4,2,1,4. (która odpowiedz i dla czego ? nie potrafie znalezc wytlumaczenia w internecie ani w wykladach). 2).Jeśli w implementacji przez listy sąsiedztwa graf nieskierowany G wygląda następująco: 1: 2->3->4 2: 1->3 3: 1->2->4 4: 1->3 to można go pokolorować a) jednym b) dwoma c) trzema d) czterema kolorami. (Jaka odpowiedz i dlaczego ? i jak bedzie sie roznil wynik gdyby graf byl skierowany.). Pozdrawiam

tumor postów: 8070	2013-02-28 12:46:10 Przede wszystkim informatyk mógłby użyć latexa. :) Macierz sąsiedztwa ma 1 tam, gdzie jakieś wierzchołki są połączone krawędzią. W przypadku grafu nieskierowanego połączenie $(1,4)$ i $(4,1)$ jest tym samym (i raczej zapiszemy $\{1,4\}$), zatem macierz powinna być symetryczna względem głównej przekątnej. Nie jest. Albo źle przepisałeś macierz, albo graf jest skierowany, albo pomylił się ktoś inny. ;) Gdyby graf był skierowany to sprawdzamy. a) cykl oznacza krawędzie (skierowane) $(1,2),(2,3)(3,1)$ Dwie pierwsze w macierzy widzimy, ale trzeciej nie, czyli odpada b) $(2,3),(3,4),(4,2)$ - tu wszystkie krawędzie odnajdujemy w macierzy c) tu w macierzy nie ma $(4,1)$ d) tu w macierzy nie ma $(2,1)$

tumor postów: 8070	2013-02-28 13:02:55 2) Zauważamy, że $\{1,2,3\}$ jest kliką (podgrafem pełnym, każde dwa z wierzchołków są połączone krawędzią). Muszą być zatem co najmniej 3 kolory. Wierzchołek 4 nie jest połączony krawędzią z 2, zatem może mieć ten sam kolor. Wystarczą 3 kolory. Oczywiście więcej ich też być może, jeśli kto chce. ;) Przy grafie skierowanym nie pomogę, chyba że mi napiszesz reguły kolorowania. Jeśli takie same, czyli (x,y) dla żadnej krawędzi skierowanej x,y nie są w jednym kolorze, to odpowiedź będzie jak dla nieskierowanego.

sebastian123 postów: 22	2013-02-28 14:57:51 Dobrze, co nieco zrozumiałem. Dziękuje Ci serdecznie, pomogles mi :)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj