Adjacency matris av en graf

< tillbaka | nästa | innehåll >

Adjacency matris: Vertex till Vertex

graffamiljen hävdar att ett av de bästa sätten att representera dem i en matris är att räkna antalet kanter mellan två intilliggande hörn.

två hörn sägs vara angränsande eller granne om den stöder minst en gemensam kant.

Låt oss börja med exempel

grafen nedan har tre hörn. Således gör vi adjacency matris av Storlek 3 med 3. Sedan sätter vi namnet på hörn på sidan av matrisen. Titta på bilden och vi börjar med en tom matris. Endast namnen på hörn finns där

för att fylla adjacency matrix

för att fylla adjacency matrix

för att fylla adjacency matrix

matris, vi tittar på vertexens namn i rad och kolumn. Om dessa hörn är anslutna med en kant eller mer räknar vi antal kanter och sätter detta nummer som matriselement.

Vertex och vertex har en gemensam kant, vi säger att Vertex och vertex är intilliggande (granne). Vi matar in antalet kant i matriscellen som motsvarar vertex och vertex .

Vertex och ligger intill en kant. Således matar vi in antalet kant i matriscellen som motsvarar Vertex och .

på samma sätt vertex och är ansluten med en kant. Således matar vi in antalet kant i matriscellen som motsvarar vertex och

det finns ingen annan kant på grafen, så vi lägger resten av ofyllda celler i matrisen som noll

matrisen för att representera en graf på detta sätt kallas adjacency matrix .

storleken på adjacency matrix är lika med antalet hörn i grafen. Det är en fyrkantig matris (det vill säga antalet rader är lika med antalet kolumner).

adjacency-matrisen för en graf är symmetrisk eftersom den inte har någon riktning. Två hörn delar samma kant kan kallas från den första till den andra, eller från den andra till den första. Till exempel Vertex och vertex har en gemensam kant, sedan element (A, b) = 1 och element (b, A) = 1.

låt oss prova ett annat exempel:

kan du göra adjacency matrix av denna graf? Prova det först innan du tittar på svaret nedan.

grafen har 3 hörn, så vi gör en matrisstorlek 3 med 3. Vi lägger namnet på hörn på sidan av matrisen.

titta Nu på vertex och vertex . Hur många kanter stöder de två vertikalerna? En. Sedan sätter vi detta värde i matrisen

titta på vertex och vertex . Hur många kanter stöder dessa hörn? Ingen. Sedan sätter vi värde noll i motsvarande cell i matrisen

nästa tittar du på vertex och vertex . Hur många kant dessa hörn stöder? Två. Sedan matar vi in matrisen i

eftersom det inte finns någon annan kant i grafen kan vi fylla den tomma cellen med nollor. Således har vi svaret

några av er kanske frågar om den diagonala delen av matrisen, är dessa celler alltid noll? Nej, Om du hittar grafen har någon slinga i vissa hörn, kan du fylla det diagonala elementet i adjacency matrix med antalet slingor.

om en graf har någon vertex som inte är ansluten till någon annan hörn, adjacency matrisen motsvarar att enda vertex är noll.

Vänligen gör lite övning för att representera grafen nedan i adjacency matrix.

(se svaret på föregående sida )

Med tanke på adjacency matrix, kan du rita tillbaka grafen?

kontrollera exempel tillämpning av grafteori I Q-lärande handledning
< tillbaka | nästa | innehåll >