macierz Adjacency grafu

< Wstecz | Dalej | Content >

macierz Adjacency: Vertex dla wierzchołków

Rodzina grafów argumentuje, że jednym z najlepszych sposobów przedstawienia ich w macierzy jest liczenie liczby krawędzi między dwoma sąsiadującymi wierzchołkami.

mówi się, że dwa wierzchołki są sąsiadujące lub sąsiadują, jeśli obsługują co najmniej jedną wspólną krawędź.

zacznijmy od przykładu

Poniższy wykres ma trzy wierzchołki. W ten sposób tworzymy macierz adjacency wielkości 3 na 3. Następnie umieszczamy nazwy wierzchołków na boku macierzy. Spójrz na obrazek i zaczynamy od pustej matrycy. Tylko nazwy wierzchołków są tam

aby wypełnić macierz adjacency, patrzymy na nazwę wierzchołka w wierszu i kolumnie. Jeśli te wierzchołki są połączone krawędzią lub więcej, liczymy liczbę krawędzi i umieszczamy tę liczbę jako element macierzy.

wierzchołek I wierzchołek ma jedną wspólną krawędź, mówimy, że wierzchołek I wierzchołek są sąsiadujące (Neighbor). Wprowadzamy liczbę krawędzi w komórce macierzy, która odpowiada wierzchołkowi I wierzchołek .

wierzchołek I sąsiaduje z jedną krawędzią. W ten sposób wpisujemy liczbę krawędzi w komórce macierzy, która odpowiada wierzchołkowi I .

podobnie, wierzchołek I jest połączona jedną krawędzią. W ten sposób wprowadzamy liczbę krawędzi w komórce macierzy, która odpowiada wierzchołkowi I

na wykresie nie ma innej krawędzi, dlatego resztę niewypełnionych komórek umieszczamy w macierzy jako zero

macierz reprezentująca wykres w ten sposób nazywana jest macierzą adjacency .

rozmiar macierzy przylegania jest równy liczbie wierzchołków na wykresie. Jest to macierz kwadratowa (czyli liczba wierszy jest równa liczbie kolumn).

macierz przylegania grafu jest symetryczna, ponieważ nie ma kierunku. Dwa wierzchołki o tej samej krawędzi mogą być wywoływane od pierwszego do drugiego lub od drugiego do pierwszego. Na przykład, Vertex I vertex ma jedną wspólną krawędź, a następnie element (A, b) = 1 i element (b, A) = 1.

wypróbujmy inny przykład:

Czy możesz zrobić macierz adjacency tego wykresu? Spróbuj najpierw, zanim spojrzysz na odpowiedź poniżej.

Wykres ma 3 wierzchołki, więc tworzymy macierz o wymiarach 3 na 3. Umieszczamy nazwy wierzchołków na boku macierzy.

teraz spójrz na wierzchołek I wierzchołek . Ile krawędzi podtrzymują dwa wierzchołki? Jeden. Następnie umieszczamy tę wartość w macierzy

spójrz na wierzchołek I wierzchołek . Ile krawędzi podtrzymują te wierzchołki? Brak Następnie umieszczamy wartość zero w odpowiedniej komórce w macierzy

następnie patrzysz na wierzchołek I wierzchołek . Ile krawędzi obsługują te wierzchołki? Dwa. Następnie wprowadzamy macierz do

ponieważ nie ma innej krawędzi w grafie, możemy wypełnić pustą komórkę zerami. Tak więc mamy odpowiedź

niektórzy z was mogą zapytać o przekątną części macierzy, czy te komórki są zawsze zerowe? Nie, jeśli okaże się, że Wykres ma jakąś pętlę w niektórych wierzchołkach, można wypełnić element diagonalny macierzy adjacency liczbą pętli.

Jeśli Wykres ma jakiś wierzchołek, który nie jest połączony z żadnym innym wierzchołkiem, to macierz przylegania odpowiada temu pojedynczemu wierzchołkowi jest równa zeru.

proszę zrobić kilka ćwiczeń, aby przedstawić Poniższy wykres w macierzy adjacency.

(Zobacz odpowiedź na poprzedniej stronie )

biorąc pod uwagę macierz adjacency, możesz narysować wykres?

Sprawdź przykładowe zastosowanie teorii grafów w samouczku Q-Learning
< Wstecz | Dalej | Content >