<Tilbake | Neste | Innhold>
Adjacency Matrise: Vertex Til Vertex
graffamilien hevder At En Av De Beste måtene Å Representere dem i en matrise er ved å telle antall kant mellom to tilstøtende hjørner.
To hjørner sies å være tilstøtende eller nabo hvis den støtter minst en felles kant.
La oss starte med eksempel
Grafen nedenfor har tre hjørner. Dermed gjør vi adjacency matrise av størrelse 3 av 3. Deretter setter vi navnet på hjørner på siden av matrisen. Se på bildet, og vi starter med en tom matrise. Bare navnene på hjørnene er der
for å fylle adjacency matrix matrise, vi ser på navnet på toppunktet i rad og kolonne. Hvis disse punktene er forbundet med en kant eller mer, teller vi antall kanter og legger dette tallet som matriseelement.
Vertex 
og vertex 
har en felles kant, sier vi At Vertex 
og vertex 
Er Tilstøtende (Nabo). Vi legger inn antall kant i matrisecellen som tilsvarer vertex 
og vertex 
.
Vertex 
og
er tilstøtende av en kant. Dermed legger vi inn antall kant i matrisecellen som tilsvarer Vertex 
og 
.
tilsvarende vertex 
og 
er forbundet med en kant. Dermed legger vi inn antall kant i matrisecellen som tilsvarer vertex 
og 
det er ingen annen kant på grafen, og dermed setter vi resten av ufylte celler i matrisen som null
matrisen å representere en graf på denne måten kalles adjacency matrix .
størrelsen på adjacency matrix er lik antall hjørner i grafen. Det er en firkantet matrise (det vil si antall rader er lik antall kolonner).
adjacency-matrisen til en graf er symmetrisk fordi den ikke har noen retning. To hjørner deler samme kant kan kalles fra den første til den andre, eller fra den andre til den første. For Eksempel Vertex 
og vertex 
har en felles kant, deretter element (a, b) = 1 og element (b, a) = 1.
la oss prøve et annet eksempel:
Kan du lage adjacency matrix av denne grafen? Prøv det først før du ser på svaret nedenfor.
grafen har 3 hjørner, slik at vi lager en matrisestørrelse 3 av 3. Vi legger navnet på hjørner på siden av matrisen.
nå ser på vertex 
og vertex
. Hvor mange kanter støtter de to hjørnene? En. Deretter setter vi denne verdien i matrisen
Se på vertex 
og vertex 
. Hvor mange kanter støtter disse hjørnene? Ingenting. Deretter setter vi verdien null i den tilsvarende cellen i matrisen
neste ser du på vertex 
og vertex 
. Hvor mange kanter støtter disse hjørnene? To. Da legger vi inn matrisen i
Siden det ikke er noen annen kant i grafen, kan vi fylle den tomme cellen med nuller. Dermed har vi svaret
Noen av dere kan spørre om den diagonale delen av matrisen, er disse cellene alltid null? Nei, hvis du finner grafen har noen sløyfe i noen hjørner, kan du fylle det diagonale elementet i adjacency matrix med antall sløyfe.
hvis en graf har noen toppunkt som ikke er koblet til noen andre toppunkter, adjacency matrise tilsvarer at enkelt toppunkt er null.
Vennligst gjør litt øvelse for å representere grafen nedenfor i adjacency matrix.
(Se svaret på forrige side)
Gitt adjacency matrix, kan du trekke tilbake grafen?
Sjekk eksempel anvendelse av grafteori I Q-Læring Opplæringen
< Tilbake | Neste/Innhold>