Tässä artikkelissa aiomme keskustella viereisyysmatriisista sen esityksen kanssa.

java-luettelomerkkijono

Vierekkäisyysmatriisin määritelmä

Graafiteoriassa viereisyysmatriisi on tiheä tapa kuvata äärellisen graafin rakennetta. Se on 2D-matriisia, jota käytetään kuvaamaan graafin solmujen välinen yhteys.

Jos kaaviossa on n pisteiden lukumäärä, niin kyseisen graafin viereisyysmatriisi on n x n , ja jokainen matriisin merkintä edustaa reunojen määrää kärjestä toiseen.

Viereisyysmatriisia kutsutaan myös nimellä yhteysmatriisi . Joskus sitä kutsutaan myös a Vertex matriisi .

Vierekkäisyysmatriisiesitys

Jos suuntaamaton graafi G koostuu n pisteestä, graafin vierekkäisyysmatriisi on n x n matriisi A = [aij] ja sen määrittelee -

a_ij= 1 {jos polku on olemassa V:stä_iV:lle_j}

a_ij= 0 {muuten}

Katsotaanpa joitain tärkeitä kohtia viereisyysmatriisin suhteen.

• Jos kärjen V välillä on reuna_ija V_j, jossa i on rivi ja j on sarake, niin a:n arvo_ij= 1.
• Jos kärjen V välillä ei ole reunaa_ija V_j, sitten a:n arvo_ij= 0.
• Jos yksinkertaisessa graafissa ei ole itsesilmukoita, niin vertex-matriisin (tai vierekkäisyysmatriisin) diagonaalissa tulee olla nollia.
• Viereisyysmatriisi on symmetrinen suuntaamattomalle graafille. Se määrittää, että i:n arvo^thrivi ja j^thsarake on yhtä suuri kuin j:n arvo^thrivi i^th
• Jos viereisyysmatriisi kerrotaan itsellään ja jos on nollasta poikkeava arvo, on i:ssä^thrivi ja j^thsarake, sitten on reitti V:stä_iV:lle_j­­jonka pituus on yhtä suuri kuin 2. Nollasta poikkeava arvo vierekkäisyysmatriisissa tarkoittaa, että eri polkuja on olemassa.

Huomautus: Vierekkäisyysmatriisissa 0 tarkoittaa, että kahden solmun välillä ei ole yhteyttä, kun taas 1 tarkoittaa, että kahden solmun välillä on yhteys.

Kuinka luoda läheisyysmatriisi?

Oletetaan, että on Graafi g kanssa n pisteiden lukumäärä, niin pistematriisi (tai vierekkäisyysmatriisi) saadaan kaavalla -

miten komentosarja suoritetaan

A = a_yksitoistaa₁₂. . . . . a_1na_{kaksikymmentäyksi}a₂₂. . . . . a_2n. . . . . . . . . a_n1a_n2. . . . . a_nn

Missä a_ijon yhtä suuri kuin reunojen lukumäärä kärjestä i pisteeseen j. Kuten edellä mainittiin, vierekkäisyysmatriisi on symmetrinen suuntaamattomalle graafille, joten suuntaamattomalle graafille_ij= a_hei.

Kun graafit ovat yksinkertaisia ​​ja reunoilla ei ole painoja tai useita reunoja, niin viereisyysmatriisin syötöt ovat 0 ja 1. Jos itsesilmukoita ei ole, viereisyysmatriisin diagonaaliset merkinnät ovat 0.

Katsotaan nyt suuntaamattoman ja suunnatun graafin viereisyysmatriisi.

Suuntaamattoman graafin vierekkäisyysmatriisi

Suuntaamattomassa graafissa reunoja ei liitetä niihin liittyviin suuntiin. Jos ohjaamattomassa graafissa kärjen A ja pisteen B välillä on reuna, niin pisteet voidaan siirtää A:sta B:hen sekä B:stä A:han.

Tarkastellaan alla olevaa suuntaamatonta graafia ja yritetään rakentaa sen viereisyysmatriisi.

mikä on java hashmap

Kaaviosta näemme, ettei itsesilmukkaa ole, joten viereisen matriisin diagonaalisyötteet ovat 0. Yllä olevan kaavion viereisyysmatriisi on -

Suunnatun graafin vierekkäisyysmatriisi

Suunnatussa graafissa reunat muodostavat järjestetyn parin. Reunat edustavat tiettyä polkua jostakin kärjestä A toiseen kärkeen B. Solmua A kutsutaan alkusolmuksi, kun taas solmua B kutsutaan terminaalisolmuksi.

Tarkastellaan alla olevaa suunnattua graafia ja yritetään rakentaa sen viereisyysmatriisi.

Yllä olevasta kaaviosta näemme, että itsesilmukkaa ei ole, joten viereisen matriisin diagonaalisyötteet ovat 0. Yllä olevan kaavion viereisyysmatriisi on -

Viereisyysmatriisin ominaisuudet

Jotkut vierekkäisyysmatriisin ominaisuuksista on lueteltu seuraavasti:

• Vierekkäisyysmatriisi on matriisi, joka sisältää rivejä ja sarakkeita, joita käytetään edustamaan yksinkertaista merkittyä kuvaajaa numeroilla 0 ja 1 kohdassa (V_minä, SISÄÄN_j), sen ehdon mukaan, ovatko kaksi V_{i ­} ja V_jovat vierekkäin.
• Suunnatun graafin kohdalla, jos kärjen i tai V välillä on reuna_iVertexiin j tai V_j, sitten A[V_i][SISÄÄN_j] = 1, muuten arvo on 0.
• Jos suuntaamattomalla graafilla on reuna, joka on olemassa kärjen i tai V välillä_iVertexiin j tai V_j, sitten A[V_i][SISÄÄN_j] = 1 ja A[V_j][SISÄÄN_i] = 1, muuten arvo on 0.

Katsotaanpa joitain vierekkäisyysmatriisin kysymyksiä. Alla olevat kysymykset koskevat painotettuja suuntaamattomia ja suunnattuja kaavioita.

HUOMAA: Graafin sanotaan olevan painotettu graafi, jos jokaiselle reunalle on määritetty positiivinen luku, jota kutsutaan reunan painoksi.

Kysymys 1 - Mikä on vierekkäisyysmatriisi alla olevalle suuntaamattomalle painotetulle graafille?

Ratkaisu - Annetussa kysymyksessä ei ole omasilmukkaa, joten on selvää, että viereisen matriisin diagonaalisyötöt yllä olevalle graafille ovat 0. Yllä oleva graafi on painotettu suuntaamaton graafi. Kuvaajan reunojen painot esitetään vierekkäisyysmatriisin syötteinä.

Yllä olevan kaavion vierekkäisyysmatriisi on -

Kysymys 2 - Mikä on vierekkäisyysmatriisi alla olevalle suunnatulle painotetulle graafille?

Ratkaisu - Annetussa kysymyksessä ei ole itsesilmukkaa, joten on selvää, että viereisen matriisin diagonaalisyötöt yllä olevalle graafille ovat 0. Yllä oleva graafi on painotettu suunnattu graafi. Kuvaajan reunojen painot esitetään vierekkäisyysmatriisin syötteinä.

Yllä olevan kaavion vierekkäisyysmatriisi on -

govinda näyttelijä

Toivottavasti tämä artikkeli on hyödyllinen sinulle, jotta ymmärrät viereisyysmatriisin. Täällä olemme keskustelleet viereisyysmatriisista sen luomisesta ja ominaisuuksista. Olemme myös keskustelleet vierekkäisyysmatriisin muodostamisesta suunnatuille tai suuntaamattomille graafille, olivatpa ne painotettuja vai ei.