Šajā rakstā mēs apspriedīsim blakusesības matricu un tās attēlojumu.

Blakusuma matricas definīcija

Grafu teorijā blakusesības matrica ir blīvs veids, kā aprakstīt ierobežoto grafu struktūru. Tā ir 2D matrica, ko izmanto, lai kartētu saistību starp grafika mezgliem.

Ja grafikā ir n virsotņu skaits, tad šī grafa blakusesības matrica ir n x n , un katrs matricas ieraksts apzīmē malu skaitu no vienas virsotnes uz otru.

Blakusuma matricu sauc arī par savienojuma matrica . Dažreiz to sauc arī par a Virsotnes matrica .

Blakus esošās matricas attēlojums

Ja nevirzītais grafiks G sastāv no n virsotnēm, tad grafa blakus matrica ir n x n matrica A = [aij] un definēta ar -

a _ij = 1 {ja ir ceļš, pastāv no V _i uz V _j }

a _ij = 0 {citādi}

Apskatīsim dažus svarīgus punktus attiecībā uz blakusesības matricu.

• Ja starp virsotni V pastāv mala _i un V _j , kur i ir rinda un j ir kolonna, tad a vērtība _ij = 1.
• Ja starp virsotni V nav malas _i un V _j , tad a vērtība _ij = 0.
• Ja vienkāršā grafikā nav pašcilpu, tad virsotņu matricas (vai blakusesības matricas) diagonālē jābūt 0.
• Blakusuma matrica ir simetriska nevirzītam grafikam. Tas norāda, ka vērtība i ^th rinda un j ^th kolonna ir vienāda ar vērtību j ^th i rinda ^th
• Ja blakusesības matrica tiek reizināta ar sevi un ja ir vērtība, kas nav nulle, i ir ^th rinda un j ^th kolonnā, tad ir maršruts no V _i uz V _{j ­ ­} ar garumu, kas ir līdzvērtīgs 2. Vērtība, kas nav nulle blakusesības matricā, norāda, ka pastāv atšķirīgu ceļu skaits.

Piezīme. Blakusuma matricā 0 norāda, ka starp diviem mezgliem nepastāv saistība, savukārt 1 norāda, ka starp diviem mezgliem pastāv saistība.

Kā izveidot blakus matricu?

Pieņemsim, ka ir grafiks g ar n virsotņu skaitu, tad virsotņu matricu (vai blakusesību matricu) dod ar -

A = a _vienpadsmit a ₁₂ . . . . . a _1n a _{divdesmitviens} a ₂₂ . . . . . a _2n . . . . . . . . . a _n1 a _n2 . . . . . a _nn

Kur atrodas a _ij ir vienāds ar malu skaitu no virsotnes i līdz j. Kā minēts iepriekš, nevirzītam grafikam blakusesības matrica ir simetriska, tāpēc nevirzītam grafikam _ij = a _hei .

Kad grafiki ir vienkārši un uz malām nav atsvaru vai vairāku malu, tad blakusesības matricas ieraksti būs 0 un 1. Ja pašcilpu nav, tad blakusesības matricas diagonālie ieraksti būs 0.

Tagad apskatīsim blakusesības matricu nevirzītam grafikam un virzītiem grafikiem.

Blakusuma matrica nevirzītam grafikam

Nevirzītā grafikā malas nav saistītas ar virzieniem ar tām. Nevirzītā grafā, ja starp virsotni A un virsotni B ir mala, tad virsotnes var pārnest no A uz B, kā arī no B uz A.

Apskatīsim zemāk esošo nevirzīto grafiku un mēģināsim izveidot tā blakusesības matricu.

Grafikā redzams, ka pašcilpas nav, tāpēc blakus esošās matricas diagonālie ieraksti būs 0. Iepriekš minētā grafika blakus matrica būs -

Blakusuma matrica virzītam grafikam

Virzītā grafā malas veido sakārtotu pāri. Malas attēlo noteiktu ceļu no kādas virsotnes A uz citu virsotni B. Mezgls A tiek saukts par sākotnējo mezglu, bet mezgls B tiek saukts par gala mezglu.

Apskatīsim tālāk norādīto grafiku un mēģināsim izveidot tā blakusesības matricu.

Iepriekš redzamajā grafikā redzams, ka pašcilpas nav, tāpēc blakus esošās matricas diagonālie ieraksti būs 0. Iepriekš minētā grafika blakus matrica būs -

Blakusuma matricas īpašības

Dažas no blakus esošās matricas īpašībām ir uzskaitītas šādi:

• Blakus matrica ir matrica, kas satur rindas un kolonnas, ko izmanto, lai attēlotu vienkāršu iezīmētu grafiku ar cipariem 0 un 1 pozīcijā (V _es , IN _j ), atkarībā no nosacījuma, vai abi V _{i ­} un V _j atrodas blakus.
• Virzītam grafam, ja starp virsotni i vai V ir mala _i uz virsotni j vai V _j , tad vērtība A[V _i ][IN _j ] = 1, pretējā gadījumā vērtība būs 0.
• Nevirzītam grafam, ja starp virsotni i vai V ir mala _i uz virsotni j vai V _j , tad vērtība A[V _i ][IN _j ] = 1 un A[V _j ][IN _i ] = 1, pretējā gadījumā vērtība būs 0.

Apskatīsim dažus blakusesības matricas jautājumus. Tālāk ir sniegti jautājumi par svērtajām nevirzītajām un virzītajām diagrammām.

PIEZĪME. Grafiks tiek uzskatīts par svērto grafiku, ja katrai malai ir piešķirts pozitīvs skaitlis, ko sauc par malas svaru.

Jautājums 1 - Kāda būs blakusesības matrica tālāk norādītajam nevirzītajam svērtajam grafikam?

Risinājums - Dotajā jautājumā pašcilpas nav, tāpēc ir skaidrs, ka blakus esošās matricas diagonālie ieraksti iepriekšminētajam grafikam būs 0. Iepriekš minētais grafiks ir svērtais nevirzītais grafs. Grafika malu svari tiks attēloti kā blakusesības matricas ieraksti.

Iepriekš minētā grafika blakus matrica būs -

2. jautājums - Kāda būs blakus esošā matrica tālāk norādītajam svērtajam grafikam?

Risinājums - Dotajā jautājumā pašcilpas nav, tāpēc ir skaidrs, ka blakus esošās matricas diagonālie ieraksti iepriekšminētajam grafikam būs 0. Iepriekš minētais grafiks ir svērtais virzīts grafs. Grafika malu svari tiks attēloti kā blakusesības matricas ieraksti.

Iepriekš minētā grafika blakus matrica būs -

Cerams, ka šis raksts jums ir noderīgs, lai izprastu blakusesību matricu. Šeit mēs esam apsprieduši blakus esošu matricu, kā arī tās izveidi un īpašības. Mēs esam arī apsprieduši blakus matricas veidošanu virzītos vai nevirzītos grafikos neatkarīgi no tā, vai tie ir svērti vai nē.