Rank (teorie grafů) - Rank (graph theory)

v teorie grafů, obor matematiky, hodnost z neorientovaný graf má dvě nesouvisející definice. Nechat $n$ stejný počet vrcholy grafu.

V teorie matic grafů hodnost $r$ neorientovaného grafu je definován jako hodnost jeho matice sousedství.

Analogicky neplatnost grafu je nullita jeho matice sousedství, která se rovná

n - r

.

V teorie matroidů grafů je hodnost neorientovaného grafu definována jako počet $n - C$ , kde $C$ je počet připojené komponenty grafu.^[1] Ekvivalentně je hodnost grafu hodnost orientovaných matice výskytu spojené s grafem.^[2]

Analogicky, neplatnost grafu je neplatnost její orientované matice dopadu dané vzorcem

m - n + C

, kde n a C jsou jako výše a m je počet hran v grafu. Nulita se rovná první Betti číslo grafu. Součet pořadí a neplatnosti je počet hran.

Příklady

Ukázkový graf a matice:

Neorientovaný graf.

(odpovídá čtyřem hranám, e1 – e4):

=

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

V tomto příkladu teorie matice hodnost matice je 4, protože její sloupcové vektory jsou lineárně nezávislé.

^ Weisstein, Eric W. „Grafové hodnocení.“ From MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html
^ Grossman, Jerrold W .; Kulkarni, Devadatta M .; Schochetman, Irwin E. (1995), „O nezletilých incidenční matici a její Smithově normální formě“, Lineární algebra a její aplikace, 218: 213–224, doi:10.1016 / 0024-3795 (93) 00173-W, PAN 1324059. Viz zejména diskuse na str. 218.

Chen, Wai-Kai (1976), Aplikovaná teorie grafůNakladatelství North Holland Publishing Company, ISBN 0-7204-2371-6.
Hedetniemi, S. T., Jacobs, D. P., Laskar, R. (1989), Nerovnosti zahrnující hodnost grafu. Journal of Combinatorial Mathematics and Combinatorial Computing, sv. 6, s. 173–176.
Bevis, Jean H., Blount, Kevin K., Davis, George J., Domke, Gayla S., Miller, Valerie A. (1997), Pořadí grafu po přidání vrcholu. Lineární algebra a její aplikace, sv. 265, s. 55–69.