W tym artykule omówimy macierz sąsiedztwa wraz z jej reprezentacją.

Definicja macierzy sąsiedztwa

W teorii grafów macierz sąsiedztwa jest gęstym sposobem opisu skończonej struktury wykresu. Jest to macierz 2D używana do mapowania powiązań pomiędzy węzłami wykresu.

Jeśli wykres ma N liczba wierzchołków, to macierz sąsiedztwa tego grafu wynosi n x n , a każdy wpis macierzy reprezentuje liczbę krawędzi od jednego wierzchołka do drugiego.

Macierz sąsiedztwa nazywana jest także tzw macierz połączeń . Czasami nazywa się to również a Macierz wierzchołków .

Reprezentacja macierzy sąsiedztwa

Jeśli graf nieskierowany G składa się z n wierzchołków, to macierz sąsiedztwa grafu ma postać n x n macierzy A = [aij] i jest zdefiniowana przez -

A _ja = 1 {jeśli istnieje ścieżka z V _I do V _J }

A _ja = 0 {W przeciwnym razie}

Przyjrzyjmy się niektórym ważnym punktom w odniesieniu do macierzy sąsiedztwa.

• Jeżeli istnieje krawędź pomiędzy wierzchołkiem V _I i V _J , gdzie i to wiersz, a j to kolumna, to wartość a _ja = 1.
• Jeśli nie ma krawędzi pomiędzy wierzchołkiem V _I i V _J , wówczas wartość a _ja = 0.
• Jeśli na prostym grafie nie ma pętli własnych, wówczas macierz wierzchołków (lub macierz sąsiedztwa) powinna mieć zera na przekątnej.
• Macierz sąsiedztwa jest symetryczna dla grafu nieskierowanego. Określa, że ​​wartość w i ^t rząd i j ^t kolumna jest równa wartości w j ^t rząd I ^t
• Jeśli macierz sąsiedztwa zostanie pomnożona przez samą siebie i jeśli w punkcie i występuje wartość różna od zera ^t rząd i j ^t kolumnie, to jest trasa z V _I do V _{J ­ ­} o długości równej 2. Niezerowa wartość w macierzy sąsiedztwa oznacza, że ​​występuje wiele różnych ścieżek.

Uwaga: W macierzy sąsiedztwa 0 oznacza, że ​​nie istnieje powiązanie między dwoma węzłami, natomiast 1 oznacza, że ​​istnieje powiązanie między dwoma węzłami.

Jak utworzyć macierz sąsiedztwa?

Załóżmy, że istnieje wykres G z N liczba wierzchołków, wówczas macierz wierzchołków (lub macierz sąsiedztwa) jest dana wzorem -

A = a _jedenaście A ₁₂ . . . . . A _1n A _{dwadzieścia jeden} A ₂₂ . . . . . A _2n . . . . . . . . . A _n1 A _n2 . . . . . A _nn

Gdzie A _ja jest równa liczbie krawędzi od wierzchołka i do j. Jak wspomniano powyżej, macierz sąsiedztwa jest symetryczna dla grafu nieskierowanego, zatem w przypadku grafu nieskierowanego _ja = za _hej .

Gdy wykresy są proste i nie ma wag na krawędziach lub wielokrotnych krawędziach, wówczas wpisy macierzy sąsiedztwa będą wynosić 0 i 1. Jeśli nie ma pętli własnych, wówczas ukośne wpisy macierzy sąsiedztwa będą wynosić 0.

Przyjrzyjmy się teraz macierzy sąsiedztwa dla grafów nieskierowanych i grafów skierowanych.

Macierz sąsiedztwa dla grafu nieskierowanego

W grafie nieskierowanym krawędzie nie są powiązane z kierunkami. W grafie nieskierowanym, jeśli pomiędzy wierzchołkiem A a wierzchołkiem B istnieje krawędź, to wierzchołki można przenieść z A do B oraz z B do A.

Rozważmy poniższy graf nieskierowany i spróbujmy skonstruować jego macierz sąsiedztwa.

Na wykresie widzimy, że nie ma pętli własnej, więc ukośne wpisy sąsiedniej macierzy będą wynosić 0. Macierz sąsiedztwa powyższego wykresu będzie miała postać -

Macierz sąsiedztwa dla grafu skierowanego

W grafie skierowanym krawędzie tworzą uporządkowaną parę. Krawędzie reprezentują określoną ścieżkę od jakiegoś wierzchołka A do innego wierzchołka B. Węzeł A nazywany jest węzłem początkowym, podczas gdy węzeł B nazywany jest węzłem końcowym.

Rozważmy poniższy graf skierowany i spróbujmy skonstruować jego macierz sąsiedztwa.

Na powyższym wykresie widzimy, że nie ma pętli własnej, więc ukośne wpisy sąsiedniej macierzy będą wynosić 0. Macierz sąsiedztwa powyższego wykresu będzie miała postać -

Własności macierzy sąsiedztwa

Niektóre właściwości macierzy sąsiedztwa są wymienione w następujący sposób:

• Macierz sąsiedztwa to macierz zawierająca wiersze i kolumny używane do przedstawienia prostego wykresu oznaczonego etykietami z liczbami 0 i 1 na pozycji (V _I , W _J ), zgodnie z warunkiem, czy dwa V _{I ­} i V _J sąsiadują.
• W przypadku grafu skierowanego, jeśli istnieje krawędź pomiędzy wierzchołkiem i lub V _I do wierzchołka j lub V _J , to wartość A[V _I ][W _J ] = 1, w przeciwnym razie wartość będzie wynosić 0.
• W przypadku grafu nieskierowanego, jeśli istnieje krawędź pomiędzy wierzchołkiem i lub V _I do wierzchołka j lub V _J , to wartość A[V _I ][W _J ] = 1 i A[V _J ][W _I ] = 1, w przeciwnym razie wartość będzie wynosić 0.

Przyjrzyjmy się kilku pytaniom dotyczącym macierzy sąsiedztwa. Poniższe pytania dotyczą grafów ważonych nieskierowanych i skierowanych.

UWAGA: Graf nazywa się grafem ważonym, jeżeli każdej krawędzi przypisano liczbę dodatnią, nazywaną wagą krawędzi.

Pytanie 1 - Jaka będzie macierz sąsiedztwa dla poniższego nieukierunkowanego grafu ważonego?

Rozwiązanie - W zadanym pytaniu nie ma pętli własnej, więc jasne jest, że ukośne wpisy sąsiedniej macierzy dla powyższego grafu będą wynosić 0. Powyższy wykres jest grafem ważonym nieskierowanym. Wagi na krawędziach wykresu będą reprezentowane jako wpisy macierzy sąsiedztwa.

Macierz sąsiedztwa powyższego wykresu będzie wynosić -

Pytanie 2 - Jaka będzie macierz sąsiedztwa dla poniższego ukierunkowanego grafu ważonego?

Rozwiązanie - W zadanym pytaniu nie ma pętli własnej, więc jasne jest, że ukośne wpisy sąsiedniej macierzy dla powyższego wykresu będą wynosić 0. Powyższy wykres jest grafem skierowanym ważonym. Wagi na krawędziach wykresu będą reprezentowane jako wpisy macierzy sąsiedztwa.

Macierz sąsiedztwa powyższego wykresu będzie wynosić -

Mam nadzieję, że ten artykuł będzie dla Ciebie przydatny i pomoże Ci zrozumieć macierz sąsiedztwa. Tutaj omówiliśmy macierz sąsiedztwa wraz z jej utworzeniem i właściwościami. Omówiliśmy także tworzenie macierzy sąsiedztwa na grafach skierowanych i nieskierowanych, niezależnie od tego, czy są one ważone, czy nie.