Gradsmatrix
I matematik , og især i grafteori , den grad matrix er en matrix , der indeholder information om graden af hvert hjørne i en graf.
Matrixen af grader er en diagonal matrix . Det bruges sammen med adjacency matrixen til at konstruere den laplaciske matrix i en graf.
Definition
Givet en graf , der indeholder knudepunkter, matrixen af grader af er den kvadratisk matrix defineret ved:
G=(V,E){\ displaystyle G = (V, E)}
ikke{\ displaystyle n}
D{\ displaystyle D}
G{\ displaystyle G}
ikke×ikke{\ displaystyle n \ times n}
djeg,j: ={grader(vjeg)hvis jeg=j0hvis ikke{\ displaystyle d_ {i, j}: = \ left \ {{\ begin {matrix} \ deg (v_ {i}) & {\ mbox {si}} \ i = j \\ 0 & {\ mbox {ellers }} \ end {matrix}} \ højre.}
Graden af toppunktet er antallet af led (kanter eller buer), der fører til dette toppunkt. Dette får hver sløjfe til at tælle som 2: hvert link har faktisk to ender, og hver af disse to ender øger graden. Ligeledes har isolerede hjørner en grad lig med 0.
I tilfælde af en rettet graf er graden af et toppunkt summen af dets indgangsgrad og dets udgående grad.
Eksempel
Mærket graf
|
Gradsmatrix
|
---|
|
(400000030000002000000300000030000001){\ displaystyle {\ begin {pmatrix} 4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\\ end} {pmatrix}
|
Bemærk, at graden af toppunkt 1 er 4: 2 for de to tilstødende hjørner 2 og 5 og 2 for sløjfen, der starter fra 1 og vender tilbage til den.
Ejendomme
- Graden matrix af en regelmæssig grad graf har en diagonal, hvis koefficienter er alle lige .k{\ displaystyle k}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Referencer
-
Krishnaiyan Thulasiraman, Grafteori , side 218
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">