그래프 열거

수학 영역인 조합학에서 그래프 열거는 특정 유형의 비방향 또는 지시된 그래프를 계산해야 하는 결합기 열거 문제의 클래스를 설명하며, 일반적으로 그래프의 정점 수의 함수로 간주한다.^[1]이러한 문제들은 정확히 (대수학 열거 문제로서) 해결되거나 점증적으로 해결될 수 있다.수학의 이 분야의 선구자는 조지 폴리야,^[2] 아서 케일리^[3], J였다. 하워드 ^[4]레드필드

레이블 지정 문제 및 레이블 지정되지 않은 문제

일부 그래픽 열거 문제에서, 그래프의 정점은 서로 구별할 수 있는 방식으로 라벨링되는 것으로 간주되는 반면, 다른 문제에서는 정점의 순열이 동일한 그래프를 형성하는 것으로 간주되므로 정점은 동일하거나 라벨링되지 않은 것으로 간주된다.일반적으로 라벨이 붙은 문제가 더 쉬운 경향이 있다.^[5]보다 일반적으로 결합 열거와 마찬가지로, Polya 열거 정리는 라벨이 부착되지 않은 문제를 라벨이 부착된 문제로 줄이는 중요한 도구다. 라벨이 부착되지 않은 각 클래스는 라벨이 부착된 개체의 대칭 등급으로 간주된다.

정확한 열거 공식

이 분야에서 중요한 결과로는 다음과 같은 것들이 있다.

• 라벨이 붙은 n-vertex 단순 비방향 그래프의^{n(n −1)/2} 수는 2개다.^[6]
• 라벨이 붙은 n-vertex 단순 지시 그래프의^{n(n −1)} 수는 2이다.^[7]
• n-vertex n-vertex 비방향 그래프의 숫자 C는_n 반복 관계를^[8] 만족한다.

${\displaystyle C_{n}=2^{n \comprac {1}{n}\sum _{k=1}^{n1}k{n \선택 k}2^{n-k \선택 \{}C_{k}} 선택.}$

n = 1, 2, 3, ...에 대해 C에_n 대한 값을 쉽게 계산할 수 있는 위치

1, 1, 4, 38, 728, 26704, 1866256, ...(OEIS의 후속 A001187)

• 라벨이 붙은 n-베르텍스 프리 트리의 수는 nⁿ⁻²(케일리의 공식)이다.
• 라벨이 부착되지 않은 n-베르텍스 애벌레의 수는 다음과^[9] 같다.

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\probloor }}$

그래프 데이터베이스

다양한 연구 그룹들이 작은 크기의 특정 속성을 가진 그래프를 나열하는 검색 가능한 데이터베이스를 제공했다.예를 들어,

• 그래프의 집
• 소형 그래프 데이터베이스

참조