Titulní matice - Degree matrix

V matematický pole teorie grafů, stupeň matice je diagonální matice který obsahuje informace o stupeň každého vrchol - to znamená počet hran připojených ke každému vrcholu.^[1] Používá se společně s matice sousedství postavit Laplaciánská matice grafu.^[2]

Definice

Daný graf ${ displaystyle G = (V, E)}$ s ${ displaystyle | V | = n}$, stupeň matice ${ displaystyle D}$ pro ${ displaystyle G}$ je ${ displaystyle n krát n}$ diagonální matice definováno jako^[1]

${ displaystyle D_ {i, j}: = left {{ begin {matrix} deg (v_ {i}) & { mbox {if}} i = j 0 & { mbox {jinak} } end {matrix}} vpravo.}$

kde stupeň ${ displaystyle deg (v_ {i})}$ vrcholu se počítá, kolikrát hrana končí v daném vrcholu. V neorientovaný graf, to znamená, že každá smyčka zvyšuje stupeň vrcholu o dva. V řízený graf, termín stupeň může odkazovat buď na nezávislý (počet příchozích hran u každého vrcholu) nebo překonat (počet odchozích hran na každém vrcholu).

Příklad

Následující neorientovaný graf má matici 6x6 stupňů s hodnotami:

Graf označený vrcholem	Titulní matice
	${ 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 konec {pmatrix}}$

poznámka, než v případě neorientovaných grafů, hrana, která začíná a končí ve stejném uzlu, se zvyšuje o +2 odpovídající hodnotu stupně (počítá se dvakrát).

Vlastnosti

Matice stupňů a k-regulární graf má konstantní úhlopříčku ${ displaystyle k}$.

Reference