matricea de adiacență a unui grafic

< Back | Next | Content >

matricea de adiacență: Vertex la Vertex

familia de grafuri susține că una dintre cele mai bune modalități de a le reprezenta într-o matrice este numărarea numărului de muchii dintre două vârfuri adiacente.

se spune că două vârfuri sunt adiacente sau vecine dacă acceptă cel puțin o margine comună.

să începem cu exemplul

graficul de mai jos are trei vârfuri. Astfel, facem matricea de adiacență de dimensiunea 3 cu 3. Apoi am pus numele vârfurilor pe partea matricei. Uită-te la imagine și începem cu o matrice goală. Doar numele nodurilor există

Matrix, ne uităm la numele vârfului în rând și coloană. Dacă aceste vârfuri sunt conectate printr-o margine sau mai multe, numărăm numărul de margini și punem acest număr ca element de matrice.

Vertex și vertex are o margine comună, spunem că Vertex și vertex sunt adiacente (vecin). Introducem numărul de muchii din celula matricei care corespund vertexului și vertex .

Vertex și este adiacentă cu o margine. Astfel, introducem numărul de muchii din celula matricială care corespund vertexului și .

în mod similar, vertex și este conectată printr-o margine. Astfel, introducem numărul de muchii din celula matricei care corespund vertexului și

nu există nici o altă margine pe grafic, astfel am pus restul de celule neumplute în matrice ca zero

matricea pentru a reprezenta un graficul în acest fel se numește matrice de adiacență .

dimensiunea matricei de adiacență este egală cu numărul de vârfuri din grafic. Este o matrice pătrată (adică numărul de rânduri este egal cu numărul de coloane).

matricea de adiacență a unui grafic este simetrică deoarece nu are direcție. Două vârfuri împărtășesc aceeași margine pot fi apelate de la primul la cel de-al doilea sau de la cel de-al doilea la primul. De exemplu, Vertex și vertex are o margine comună, apoi element (A, b) = 1 și element (b, A) = 1.

să încercăm un alt exemplu:

puteți face matricea de adiacență a acestui grafic? Încercați mai întâi înainte de a vă uita la răspunsul de mai jos.

graficul are 3 vârfuri, astfel facem o dimensiune a matricei 3 cu 3. Am pus numele vârfurilor pe partea matricei.

acum uita-te la vertex și vertex . Câte muchii suportă cele două vârfuri? Unu. Apoi am pus această valoare în matricea

uita-te la vertex și vertex . Câte muchii suportă aceste vârfuri? Niciuna. Apoi, am pus valoarea zero în celula corespunzătoare din matricea

apoi, te uiți la vertex și vertex . Câte muchii suportă aceste vârfuri? Doi. Apoi introducem matricea în

deoarece nu există altă margine în grafic, putem umple celula goală cu zerouri. Astfel, avem răspunsul

unii dintre voi s-ar putea întreba despre partea diagonală a matricei, sunt aceste celule întotdeauna zero? Nu, dacă găsiți că graficul are o buclă în unele vârfuri, puteți umple elementul diagonal al matricei de adiacență cu numărul de buclă.

dacă un graf are un nod care nu este conectat la alte noduri, matricea de adiacență corespunde acelui nod unic este zero.

vă rugăm să faceți unele practici pentru a reprezenta graficul de mai jos în matricea de adiacență.

(a se vedea răspunsul în pagina anterioară)

având în vedere matricea de adiacență, puteți trage înapoi graficul?

verificați exemplu de aplicare a teoriei grafurilor În Q-Learning Tutorial
< Back | Next | Content >