<Back | Next | Content>
Adjacency Matrix: Vertex to Vertex
graafiperhe väittää, että yksi parhaista tavoista esittää ne matriisiksi on laskea kahden vierekkäisen verticesin välisten reunojen lukumäärä.
kahden kärjen sanotaan olevan vierekkäisiä tai naapureita, jos se tukee vähintään yhtä yhteistä reunaa.
aloitetaan esimerkillä
alla olevassa kaaviossa on kolme kärkipistettä. Siten teemme adjacency matriisi Koko 3 mennessä 3. Sitten laitamme nimi vertices puolella matriisi. Katso kuvaa ja aloitamme tyhjällä matriisilla. Vain verteksien nimet ovat olemassa
täyttää adjacency matriisi, katsomme nimi huippupiste rivi ja sarake. Jos nämä vertices on yhdistetty reuna tai enemmän, me laskea useita reunoja ja laittaa tämän numeron matriisi Elementti.
Vertex 
and vertex 
has one common edge, we say that Vertex 
and vertex 
are adjacent (neighborhood). Syötämme matriisisoluun reunan määrän, joka vastaa vertex 
ja vertex 
.
Vertex 
and 
is adjust by one edge. Näin syötämme matriisisoluun reunan määrän, joka vastaa Vertex 
ja 
.
vastaavasti vertex 
ja 
is connected by one edge. Näin syötämme matriisisoluun reunan määrän, joka vastaa vertex 
and 
kuvaajassa ei ole muuta reunaa, joten pistämme matriisin loput täyttämättömät solut nollaksi
matriisi esittää a graafia tällä tavalla kutsutaan adjacency matrixiksi .
adjacency matriisin koko on yhtä suuri kuin kuvaajan kärkipisteiden lukumäärä. Se on neliömatriisi (eli rivien määrä on yhtä suuri kuin sarakkeiden määrä).
graafin adjasenssimatriisi on symmetrinen, koska sillä ei ole suuntaa. Kaksi samaa särmää jakavaa kärkipistettä voidaan kutsua ensimmäisestä toiseen tai toisesta ensimmäiseen. Esimerkiksi Vertex 
ja vertex 
on yksi yhteinen reuna, sitten elementti (A, b) = 1 ja elementti (b, A) = 1.
kokeillaanpa toista esimerkkiä:
voitko tehdä adjacency matrix tämän kaavion? Kokeile ensin ennen kuin katsot vastauksen alta.
kaaviossa on 3 kärkipistettä, joten teemme matriisin koon 3 by 3. Laitamme nimi vertices puolella matriisi.
nyt katsokaa vertex 
ja vertex 
. Kuinka monta reunaa nämä kaksi pistettä tukevat? Yksi. Sitten laitetaan tämä arvo matriisiin
Look at vertex 
and vertex 
. Kuinka monta reunaa nämä vertices tukevat? Kukaan. Sitten laitetaan matriisin vastaavalle solulle arvo nolla
seuraavaksi katsotaan vertex 
ja vertex 
. Kuinka monta reunaa nämä vertices tukevat? Kaksi. Sitten syötämme matriisin
koska kuvaajassa ei ole muuta reunaa, voimme täyttää tyhjän solun nollilla. Näin saadaan vastaus
jotkut teistä voivat kysyä matriisin diagonaaliosasta, ovatko nämä solut aina nolla? Ei, jos löydät kuvaajan on joitakin silmukka joissakin vertices, voit täyttää diagonaalinen Elementti adjacency matriisi määrä silmukka.
Jos kuvaajassa on jokin huippupiste, jota ei ole liitetty mihinkään muuhun kärkipisteeseen, adjacency matrix vastaa, että yksittäinen huippupiste on nolla.
tee jonkin verran harjoitusta, jotta alla oleva kuvio voidaan esittää adjacency-matriisiksi.
(Katso vastaus edelliseltä sivulta)
koska adjacency matrix, voit vetää kaavion takaisin?
Check example application of graph theory in Q-Learning Tutorial
< Back / Next / Content >