그래프 속성

예시 그래프, 평면이며 연결되고 순서 6, 크기 7, 직경 3, 둘레 3, 정점 연결 1, 도 시퀀스 <3, 3, 3, 2, 1, 2, 1

그래프 이론에서 그래프 속성이나 그래프 불변성은 그래프의 특정 라벨이나 도면과 같은 그래프 표현에 의존하지 않고 추상적 구조에만 의존하는 그래프의 속성이다.^[1]

정의들

그래프 그리기와 그래프 표현은 그래프 이론에서 유효한 주제인 반면, 그래프의 추상적 구조에만 초점을 맞추기 위해 그래프 속성은 그래프의 가능한 모든 이형화 하에서 보존되는 속성으로 정의된다.즉, 그래프 자체의 속성이며, 그래프의 특정 도면이나 표현의 속성이 아니다.비공식적으로 "그래프 불변성"이라는 용어는 정량적으로 표현되는 속성에 사용되며, "속성"은 보통 그래프의 서술적 특성화를 가리킨다.예를 들어 "그래프가 1도 정점을 가지지 않는다"는 문장은 "속성"인 반면 "그래프의 1도 정점의 개수"는 "불변성"이다.

좀 더 공식적으로, 그래프 속성은 두 개의 이형성 그래프가 모두 클래스에 속하거나 둘 다 클래스에 속하지 않는 속성을 가진 그래프의 한 클래스다.^[1]동등하게, 그래프 속성은 클래스의 지표함수, 그래프에서 부울 값까지의 함수를 사용하여 공식화될 수 있으며, 그렇지 않으면 두 개의 이형성 그래프는 서로 동일한 함수 값을 가져야 한다.그래프 불변량 또는 그래프 매개변수는 두 개의 이형성 그래프에 대해 동일한 값을 갖는 정수, 실수, 숫자의 순서 또는 다항식과 같은 그래프에서 광범위한 값의 범주에 이르는 함수로서 유사하게 공식화될 수 있다.^[2]

속성 속성

많은 그래프 속성은 그래프에 정의된 특정 자연적 부분 순서 또는 사전 순서와 관련하여 올바르게 동작한다.

속성 P가 있는 그래프의 모든 유도 하위 그래프도 속성 P가 있으면 그래프 속성 P가 유전된다.예를 들어, 완벽한 그래프가 되거나 화음 그래프가 되는 것은 유전적 특성이다.^[1]
속성 P가 있는 그래프의 모든 하위 그래프에도 속성 P가 있으면 그래프 속성은 단조롭다.예를 들어, 초당적 그래프가 되거나 삼각형이 없는 그래프가 되는 것은 단조로운 것이다.모든 단조로운 속성은 유전적인 것이지만, 반드시 그 반대는 아니다. 예를 들어, 코드 그래프의 하위 그래프는 반드시 화음인 것은 아니기 때문에 화음 그래프가 되는 것은 단조로운 것이 아니다.^[1]
속성 P가 있는 그래프의 모든 그래프 마이너도 속성 P를 가질 경우 그래프 속성은 마이너 닫힌다.예를 들어 평면 그래프가 되는 것은 약간 닫힌다.모든 마이너 클로즈드 속성은 단조롭지만, 그 반대의 경우도 아니다. 예를 들어, 삼각형이 없는 그래프의 마이너리티가 반드시 삼각형이 없는 것은 아니다.^[1]

이러한 정의는 그래프의 속성에서 숫자로 확장될 수 있다. 즉, 그래프 불변성을 공식화하는 함수가 그래프의 해당 부분 순서에서 실제 숫자로 단조함수를 형성하는 경우 그래프 불변성은 유전, 단조함수 또는 마이너 닫힘이다.

또한 그래프 불변성은 그래프 결합 해제와 관련하여 그들의 행동에 대해 연구되었다.

그래프 불변량은 두 그래프 G와 H 모두에 대해 G와 H의 불변합 결합에 대한 불변합물의 값이 G와 H에 대한 값의 합이라면 가법이다.예를 들어 정점의 수는 가법적이다.^[1]
두 그래프 G와 H 모두에 대해 G와 H의 불연속 조합에 대한 불변량 값이 G와 H에 대한 값의 산물인 경우 그래프 불변량은 곱이다.예를 들어 호소야 지수(매칭 수)는 승수다.^[1]
두 그래프 G와 H 모두에 대해 G와 H의 불연속 조합에 대한 불변량 값이 G와 H에 대한 값의 최대값이면 그래프 불변량은 최대값이다.예를 들어, 색수는 최대값이다.^[1]

또한 그래프 속성은 그래프가 리디렉션되지 않았는지 지시되었는지 여부, 다중 그래프에 해당 속성을 적용하는지 등, 그래프 속성이 설명하는 그래프 유형에 따라 분류할 수 있다.^[1]

불변제 값

그래프 불변성을 정의하는 함수의 목표 집합은 다음 중 하나일 수 있다.

그래프 속성의 지표 함수에 대한 참 또는 거짓의 진리 값.
그래프의 정점 수 또는 색채 수와 같은 정수.
그래프의 부분 색도 번호와 같은 실제 숫자.
그래프의 도 순서와 같은 정수의 순서.
그래프의 Tutte 다항식과 같은 다항식.

그래프 불변성 및 그래프 이형성

쉽게 계산할 수 있는 그래프 불변성은 그래프 이형성 또는 오히려 비이형성을 빠르게 인식하는 데 중요한데, 어떤 불변성의 경우 값이 다른 두 개의 그래프는 (정의상) 이형성을 가질 수 없기 때문이다.그러나 동일한 불변성을 가진 두 개의 그래프는 이형성일 수도 있고 아닐 수도 있다.

불변성 I(G)와 I(H)의 정체성이 그래프 G와 H의 이형성을 내포하는 경우 그래프 불변성 I(G)를 완전이라고 부른다. 효율적으로 계산이 가능한 불변성(그래프 시성 문제)을 찾는 것은 도전적인 그래프 이형성 문제에 대한 쉬운 해결책을 의미할 것이다.그러나 색소 다항식 같은 다항식 값 불변량도 대개 완전하지 않다.예를 들어, 4개의 꼭지점의 클로 그래프와 경로 그래프는 모두 동일한 색도 다항식을 가진다.

예

특성.

정수불변량

순서, 정점 수
크기, 가장자리 수
연결된 구성 요소의 수
회로 순위, 가장자리 수, 정점 및 구성 요소의 선형 조합
직경, 정점 쌍 사이의 최단 경로 길이 중 가장 긴 길이
둘레, 최단 사이클의 길이
정점 연결, 제거가 그래프의 연결을 끊는 정점의 최소 개수
가장자리 연결, 제거로 그래프의 연결이 끊기는 가장 작은 가장자리 수
색수, 적절한 색상에서 정점에 대한 최소 색상 수
적절한 가장자리 색상에서 가장자리에 대한 가장 작은 색상 수인 색지수
선택성(또는 목록 색도 번호), G가 k-선택 가능한 최소 숫자 k
독립성 번호, 독립된 정점 집합의 가장 큰 크기
전체 서브그래프 중 가장 큰 순서인 클라이크 번호
수목성
그래프속
페이지 번호
호소야 지수
위너지수
콜린 드 베르디에르 그래프 불변성
박스시티

실수불변제

시퀀스 및 다항식

학위순
그래프 스펙트럼
인접 행렬의 특성 다항식
$색도$ 다항식, $k$ $k$ 의 $k$ 개수 - k $k$ 의 함수로 간주됨
Tutte 다항식(Tutte polynomial), 그래프 연결의 많은 부분을 인코딩하는 이바리테 함수

참고 항목

세습 재산
그래프 속성 지정에 사용되는 여러 공식 언어 중 하나인 그래프 논리
화학 그래프 이론에서 밀접하게 연관된 개념인 위상학 지수

참조

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Lovász, László (2012), "4.1 Graph parameters and graph properties", Large Networks and Graph Limits, Colloquium Publications, vol. 60, American Mathematical Society, pp. 41–42.
^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "3.10 Graph Parameters", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 54–56, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.

[l-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Lovász, László (2012), "4.1 Graph parameters and graph properties", Large Networks and Graph Limits, Colloquium Publications, vol. 60, American Mathematical Society, pp. 41–42.

[2] Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "3.10 Graph Parameters", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 54–56, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.

[1]

[2]

Search