Inne, zadanie nr 494

Autor	Zadanie / Rozwiązanie
rra postów: 51	2012-06-26 08:26:48 Zadanie 1 Narysować grafy cykliczne $C_{3} i C_{4}$. Podaj ich macierze sąsiedztwa. Zadanie 2 Narysować digrafy reprezentujące permutacje: a) $\delta ={1 2 3 4 5 6 7 \choose 2 7 1 5 3 6 4}$. b) $\delta ={1 2 3 4 5 6 7 \choose 7 5 2 6 3 4 1}$. C) kiedy digraf reprezentujący permutację $\delta$ nie zawiera pętli?

tumor postów: 8070	2012-09-17 08:47:52 Macierz sąsiedztwa ma $1$ na miejscu $a_{ij}$, jeśli wierzchołki $i,j$ są połączone w tym grafie krawędzią. Na podstawie poniższych macierzy sąsiedztwa można sobie rysunki zrobić. :) $ \begin{array}{ccc} 0&&1&&1\\ 1&&0&&1\\ 1&&1&&0 \end{array}$ $ \begin{array}{cccc} 0&&1&&0&&1\\ 1&&0&&1&&0\\ 0&&1&&0&&1\\ 1&&0&&1&&0 \end{array}$ I uwaga mała, dla grafu cyklicznego wystarczy, żeby wierzchołki były połączone w jeden cykl, nie muszą być w kolejności 1,2,3,4 (dla $C_3$ ta uwaga jest bez znaczenia). Wiadomość była modyfikowana 2012-09-17 08:49:36 przez tumor

tumor postów: 8070	2012-09-17 08:58:14 Zadanie 2. a) graf skierowany ma "strzałki" zamiast krawędzi. Zapis $(a,b)$ oznacza strzałkę od $a$ do $b$ Graf w tym przykładzie składa się z wierzchołków $1,2,3,4,5,6,7$ i krawędzi skierowanych: $(1,2), (2,7),(3,1), (4,5), (5,3),(6,6), (7,4)$ Przy czym krawędź $(6,6)$ to pętla, czyli strzałka od wierzchołka $6$ do niego samego. b) $(1,7), (2,5), (3,2), (4,6), (5,3), (6,4), (7,1)$ c) kiedy permutacja nie ma punktów stałych, czyli kiedy macierz sąsiedztwa ma same zera na przekątnej

strony: 1

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