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

rodzaje testowania oprogramowania

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_Ido V_J}

A_ja= 0 {W przeciwnym razie}

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

Java podwójnie na ciąg

• Jeżeli istnieje krawędź pomiędzy wierzchołkiem V_Ii 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_Ii 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^trząd i j^tkolumna jest równa wartości w j^trzą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^trząd i j^tkolumnie, to jest trasa z V_Ido 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ścieA₁₂. . . . . A_1nA_{dwadzieścia jeden}A₂₂. . . . . A_2n. . . . . . . . . A_n1A_n2. . . . . A_nn

Gdzie A_jajest 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_Jsąsiadują.
• W przypadku grafu skierowanego, jeśli istnieje krawędź pomiędzy wierzchołkiem i lub V_Ido 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_Ido 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.

Java uzyskać aktualny czas

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.

a b c liczby

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.