Adjacency Matrice af en graf

< tilbage | næste | indhold >

Adjacency Matrice: toppunkt til toppunkt

Graffamilien hævder, at en af de bedste måder at repræsentere dem i en matrice er ved at tælle antallet af kanter mellem to tilstødende hjørner.

to hjørner siges at være tilstødende eller nabo, hvis det understøtter mindst en fælles kant.

lad os starte med eksempel

grafen nedenfor har tre hjørner. Således laver vi adjacency matrice af størrelse 3 med 3. Så sætter vi navnet på hjørner på siden af matricen. Se på billedet, og vi starter med en tom matrice. Kun navnene på hjørner er der

for at udfylde Grafteori Tutorial: Adjacency matrice

for at udfylde adjacency matrice, vi ser på navnet på toppunktet i række og kolonne. Hvis disse hjørner er forbundet med en kant eller mere, tæller vi antallet af kanter og sætter dette tal som matricselement.

toppunkt og toppunkt har en fælles kant, vi siger, at toppunkt og toppunkt er tilstødende (nabo). Vi indtaster antallet af kant i matricen celle, der svarer til toppunkt og toppunkt .

toppunkt og støder op til en kant. Således indtaster vi antallet af kant i matricen celle, der svarer til toppunkt og .

tilsvarende toppunktog er forbundet med en kant. Således indtaster vi antallet af kant i matricen celle, der svarer til toppunkt og

Der er ingen anden kant på grafen, således sætter vi resten af ufyldte celler i matricen som nul

matricen til at repræsentere en graf på denne måde kaldes adjacency matricen .

størrelsen af adjacency matricen er lig med antallet af hjørner i grafen. Det er en firkantet matrice (det vil sige antallet af rækker er lig med antallet af kolonner).

adjacency matricen af en graf er symmetrisk, fordi den ikke har nogen retning. To hjørner deler den samme kant kan kaldes fra den første til den anden eller fra den anden til den første. For eksempel toppunkt og toppunkt har en fælles kant, derefter element (a, b) = 1 og element (b, A) = 1.

lad os prøve et andet eksempel:

kan du lave adjacency matricen af denne graf? Prøv det først, før du ser på svaret nedenfor.

grafen har 3 hjørner, så vi laver en matrice Størrelse 3 med 3. Vi sætter navnet på hjørner på siden af matricen.

se nu på toppunktet og toppunkt . Hvor mange kanter understøtter de to hjørner? En. Så sætter vi denne værdi i matricen

se på toppunkt og toppunkt . Hvor mange kanter understøtter disse hjørner? Ingen. Derefter sætter vi værdi nul i den tilsvarende celle i matricen

næste, du ser på toppunkt og toppunkt . Hvor mange kant disse hjørner understøtter? To. Derefter indtaster vi matricen i

da der ikke er nogen anden kant i grafen, kan vi fylde den tomme celle med nuller. Således har vi svaret

Hvis en graf har et toppunkt, der ikke er forbundet til andre hjørner, svarer adjacensmatricen til det enkelte toppunkt er nul.

vær venlig at gøre noget for at repræsentere grafen nedenfor i adjacency matrice.

(se svaret på forrige side)

i betragtning af adjacency matricen, kan du trække grafen tilbage?

tjek eksempel anvendelse af grafteori i tutorial
< tilbage | næste | indhold >