Rank (grafteori)

I grafteorin , en gren av matematiken, har rangordningen för en oriktad graf två orelaterade definitioner. Låt $n$ vara lika med antalet hörn i grafen.

I matristeorin för grafer definieras rangordningen $r för en oriktad graf som rangordningen för dess$ närliggande matris .

Analogt är nulliteten för grafen nulliteten för dess närliggande matris, vilket är lika med

n - r

.

I matroidteorin för grafer definieras rangordningen för en oriktad graf som antalet $n - c$ , där $c$ är antalet sammankopplade komponenter i grafen. På motsvarande sätt är rankningen av en graf rankningen av den orienterade incidensmatrisen som är associerad med grafen.

Analogt är nulliteten för grafen nulliteten för dess orienterade incidensmatris, givet av formeln

m - n + c

, där n och c är som ovan och m är antalet kanter i grafen. Nulliteten är lika med det första Betti-talet i grafen. Summan av rangen och nulliteten är antalet kanter.

Exempel

En exempelgraf och matris:

En oriktad graf.

(motsvarande de fyra kanterna, e1–e4):

	1	2	3	4
1	0	1	1	1
2	1	0	0	0
3	1	0	0	1
4	1	0	1	0

=

${\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&1\\1&0&1&0\\\end{pmatrix}}.$

I det här exemplet är matristeorin för matrisen 4, eftersom dess kolumnvektorer är linjärt oberoende.

Se även

Anteckningar

^ Weisstein, Eric W. "Graph Rank." Från MathWorld - En Wolfram webbresurs. http://mathworld.wolfram.com/GraphRank.html
^ Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "On the minors of an incidence matrix and its Smith normal form", Linear Algebra and Its Applications , 218 : 213–224, doi : 10.1016/0024-3795(93)00173-W , MR 1324059 . Se särskilt diskussionen på sid. 218.

Chen, Wai-Kai (1976), Applied Graph Theory , North Holland Publishing Company, ISBN 0-7204-2371-6 .
Hedetniemi, ST, Jacobs, DP, Laskar, R. (1989), Inequalities involving the rank of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing , vol. 6, s. 173–176.
Bevis, Jean H., Blount, Kevin K., Davis, George J., Domke, Gayla S., Miller, Valerie A. (1997), The rank of a graph after vertex addition . Linear Algebra and its Applications , vol. 265, s. 55–69.

[1] Weisstein, Eric W. "Graph Rank." Från MathWorld - En Wolfram webbresurs. http://mathworld.wolfram.com/GraphRank.html

[2] Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "On the minors of an incidence matrix and its Smith normal form", Linear Algebra and Its Applications , 218 : 213–224, doi : 10.1016/0024-3795(93)00173-W , MR 1324059 . Se särskilt diskussionen på sid. 218.