Frucht 그래프
Frucht graph| Frucht 그래프 | |
|---|---|
 Frucht 그래프 | |
| 이름을 따서 명명됨 | 로버트 프루히트 |
| 정점 | 12 |
| 가장자리 | 18 |
| 반지름 | 3 |
| 지름 | 4 |
| 둘레 | 3 |
| 자동형성 | 1({id}) |
| 색수 | 3 |
| 색도 지수 | 3 |
| 특성. | 큐빅 할린 범순환 |
| 그래프 및 모수 표 | |
그래프 이론의 수학적 분야에서 Frucht 그래프는 정점 12개, 가장자리 18개, 비교 대칭이 없는 3-정규 그래프다.[1]1939년 로버트 프루히트에 의해 처음 묘사되었다.[2]
Frucht 그래프는 색도 번호 3, 색도 지수 3, 반지름 3, 지름 4의 범순환 할린 그래프다.모든 할린 그래프와 마찬가지로 Frucht 그래프는 다면체(평면 및 3Vertex 연결)와 해밀턴어로, 둘레 3이다.독립번호는 5번이다.
Frucht 그래프는 LCF 표기법 [-5,-2,-4,2,5,-2,5,-2,-5,-5,-5,4,2]에서 구성할 수 있다.
대수적 특성
Frucht 그래프는 단일 그래프 자동형, 즉 정체성[3](모든 꼭지점을 다른 모든 꼭지점과 위상적으로 구별할 수 있음)만을 가진 5개의 가장 작은 입방 그래프 중 하나이다.이러한 그래프를 비대칭(또는 ID) 그래프라고 한다.Frucht의 정리는 어떤 집단이든 그래프의 대칭집단으로 실현될 수 있다고 말하고,[2] Frucht에 의한 이 정리의 강화 역시 3-정규 그래프의 대칭으로 실현될 수 있다고 기술하고 있다;[4] Frucht 그래프는 사소한 집단에 대해서도 이러한 실현의 예를 제공한다.
The characteristic polynomial of the Frucht graph is .
갤러리
Frucht 그래프의 색수는 3이다.
Frucht 그래프는 Hamiltonian이다.
참고 항목
 | 위키미디어 커먼즈에는 Frucht 그래프와 관련된 미디어가 있다. |
참조
- ^ Weisstein, Eric W. "Frucht Graph". MathWorld.
- ^ a b Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
- ^ Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976), Computer investigation of cubic graphs, EUT report, vol. 76-WSK-01, Dept. of Mathematics and Computing Science, Eindhoven University of Technology
- ^ Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987.
