Gradmatris

Från Wikipedia
Hoppa till navigering Hoppa till sök

Inom grafteorin är en gradmatris eller valensmatris en diagonalmatris som anger graden has varje nod (det vill säga hur många kanter som ansluter till respektive nod).[1] Den används tillsammans med grannmatrisen för att beräkna grafens laplacematris.[2][3][4]

Definition[redigera | redigera wikitext]

Gradmatrisen för en graf med är en diagonalmatris definierad som:[1][4]

där graden för en nod anger hur många kanter som ansluter till densamma (för en oriktad graf innebär detta att varje loop/ögla, en kant som ansluter noden till sig själv, ökar graden med två). Hos en riktad graf kan grad antingen avse ingrad (antalet kanter som går till noden) eller utgrad (antalet kanter som går från noden).

Exempel[redigera | redigera wikitext]

Graf med märkta hörn Gradmatris
6n-graph2.svg

Egenskaper[redigera | redigera wikitext]

Gradmatrisen till en k-reguljär graf har en diagonal bestående av konstanten k.

Referenser[redigera | redigera wikitext]

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.
  1. ^ [a b] Weisstein, Eric W, Degree matrix på Wolfram MathWorld.
  2. ^ Bojan Mohar, Graph Laplacians, i Lowell W. Beineke, Robin J. Wilson, 2004, Topics in Algebraic Graph Theory, sid. 113ff, ISBN 9780521801973.
  3. ^ Weisstein, Eric W, Lapalcian matrix på Wolfram MathWorld.
  4. ^ [a b] Owen Jones, 2013, Spectra of Simple Graphs, sid. 6.