순위(그래프 이론)

수학의 한 분야인 그래프 이론에서, 방향을 잡지 않은 그래프의 순위는 두 개의 관련 없는 정의를 가지고 있다. $n$ 을 그래프의 정점 수와 같게 두십시오.

이와 유사하게, 그래프의 무효는 인접 행렬의 무효로,

n

-

r

과 같다.

그래프의 매트로이드 이론에서 비방향 그래프의 순위는 $n$ - c $수로$ 정의된다. 여기서 $c$ 는 그래프의 연결된 성분의 수입니다.^[1]동등하게, 그래프의 순위는 그래프와 관련된 중심 발생 행렬의 순위다.^[2]

유사하게, 그래프의 null은

m

-

n

+

c

공식에 의해 주어지는 그것의 지향적인 발생 행렬의 null이다. 여기서 n과 c는 위와 같고 m은 그래프에 있는 가장자리 수입니다.무효는 그래프의 첫 번째 베티 번호와 같다.순위와 무효의 합은 가장자리 수입니다.

예

표본 그래프 및 행렬:

방향 지정되지 않은 그래프.

(네 개의 가장자리, e1–e4):

=

${\pmatrix}0&1&1&1\\1&0&0&0\\1&0&1\\nd{pmatrix}.$

이 예제에서 행렬의 행렬 이론 순위는 4인데, 그 열 벡터는 선형적으로 독립적이기 때문이다.

^ Weisstein, Eric W. "그래프 랭크" MathWorld-- Wolfram Web Resource.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. 특히 218페이지의 토론을 보라.

Chen, Wai-Kai (1976), Applied Graph Theory, North Holland Publishing Company, ISBN 0-7204-2371-6.
Hedetniemi, S. T, Jacobs, D. P, Laskar, R. (1989), 그래프의 순위를 포함하는 불평등.제6권, 페이지 173–176의 결합수학 및 결합수학 계산 저널.
베비스, 장 H, 블라운트, 케빈 K, 데이비스, 조지 J, 돔케, 게일라 S, 밀러, 발레리 A.(1997) 정점 추가 후 그래프의 순위.선형 대수 및 그 적용, 제265, 페이지 55–69.