큐빅 그래프

그래프 이론의 수학적 분야에서 입방 그래프는 모든 정점이 도 3을 갖는 그래프다.즉 큐빅 그래프는 3정형 그래프다.입방형 그래프를 3가 그래프라고도 한다.

이큐빅 그래프는 입방체의 초당적 그래프다.

대칭

1932년, 로널드 M. 포스터는 포스터 인구 조사의 시작을 형성하면서 입방 대칭 그래프의 예를 수집하기 시작했다.^[1]Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph.W. T. Tutte는 대칭 입방 그래프를 가장 작은 정수 s로 분류하여 길이 s의 각 두 방향 경로를 그래프의 정확히 하나의 대칭으로 서로 매핑할 수 있도록 했다.그는 s가 최대 5라는 것을 보여주었고, 1에서 5까지의 각 가능한 s 값을 가진 그래프의 예를 제공했다.^[2]

반대칭 입방형 그래프에는 그레이 그래프(최소 반대칭 입방형 그래프), 류블랴나 그래프, 투테 12케이지 등이 있다.

Frucht 그래프는 대칭이 없는 5개의 가장 작은 입방형 그래프 중 하나이다.^[3] 그것은 오직 하나의 그래프 자동형, 즉 정체성 자동형만을 가지고 있다.^[4]

컬러링 및 독립 세트

브룩스의 정리에 따르면 전체 그래프 K를₄ 제외한 연결된 모든 입방 그래프는 최대 3가지 색상으로 채색할 수 있다.따라서 K를₄ 제외한 모든 연결된 입방형 그래프에는 최소 n/3 정점의 독립된 집합이 있으며, 여기서 n은 그래프에서 정점의 수입니다. 예를 들어, 3-색상에서 가장 큰 색상 등급은 적어도 정점의 수가 이만큼 된다.

Vizing의 정리에 따르면 모든 세제곱 그래프는 가장자리 색상을 위해 서너 가지 색상을 필요로 한다.3-엣지 컬러링은 태트 컬러링으로 알려져 있으며, 그래프의 가장자리 부분을 세 개의 완벽한 매칭으로 분할한다.Kőnig의 선 컬러링 정리법에 의해 모든 바이큐빅 그래프는 태트 컬러링을 가지고 있다.

타이트 색상이 없는 브리지리스 큐빅 그래프는 스나크라고 알려져 있다.피터슨 그래프, 티에체 그래프, 블라누샤 스나크, 꽃 스나크, 더블스타 스나크, 스체크레스 스나크, 왓킨스 스나크 등이 그것이다.뚜렷한 스나크가 무한히 있다.^[5]

위상 및 기하학

입방 그래프는 여러 가지 방법으로 토폴로지에서 자연적으로 발생한다.예를 들어, 어떤 사람이 그래프를 1차원 CW 콤플렉스로 간주한다면, 입방 그래프는 대부분의 1-셀 부착 맵이 그래프의 0-골격과 분리된다는 점에서 일반적이다.입방형 그래프는 또한 3차원의 간단한 다면체의 그래프로서 형성되는데, 3개의 면이 모든 꼭지점에서 만나는 특성을 가진 일반 도면체 같은 다면체도이다.

2차원 표면에 포함된 임의의 그래프는 그래프 인코딩 맵으로 알려진 입방형 그래프 구조로 나타낼 수 있다.이 구조에서 입방 그래프의 각 꼭지점은 임베딩의 깃발을 나타내며, 표면의 꼭지점, 가장자리, 면의 상호 입사 3배이다.각 국기의 세 이웃은 세 개의 국기로서 이 상호 사건 세 개의 구성원 중 한 명을 변경하고 나머지 두 명의 멤버는 변경하지 않음으로써 얻을 수 있는 세 개의 국기다.^[6]

해밀턴시티

입방형 그래프의 해밀턴성에 대한 많은 연구가 있었다.1880년에 P.G. Tait는 모든 입방체 다면체 그래프에 해밀턴 회로가 있다고 추측했다.윌리엄 토머스 투테는 1946년 46베르텍스 투테 그래프인 타이트의 추측에 대한 반례를 제공했다.1971년에 투테는 모든 바이큐빅 그래프가 해밀턴식이라고 추측했다.그러나 조셉 호튼은 96개의 꼭지점에 대한 counterexample, 즉 호튼 그래프를 제공했다.^[7]후에, 마크 엘링햄은 두 개의 백작샘플을 더 만들었다: 엘링햄-호튼 그래프.^[8][9]태트와 투테의 추측의 여전히 열려 있는 조합인 바넷의 추측에 의하면 모든 바이큐빅 다면체 그래프는 해밀턴이라고 한다.입방 그래프가 해밀턴식일 때, LCF 표기법은 그것을 간결하게 나타낼 수 있게 한다.

모든 n-vertex 입방형 그래프 중에서 입방형 그래프를 무작위로 균일하게 선택하면 해밀턴식일 가능성이 매우 높다: 해밀턴식인 n-Vertex 입방형 그래프의 비율은 n이 무한대로 가면서 한계에 있는 경향이 있다.^[10]

데이비드 엡스타인은 모든 n-Vertex 입방 그래프는 최대 2회^n/3(약 1.260ⁿ)의 구별되는 해밀턴 사이클을 가지고 있다고 추측하고, 그렇게 많은 사이클을 가진 입방 그래프의 예를 제공했다.^[11]구별되는 해밀턴 주기 수에 대한 가장 잘 입증된 추정치는 $O{\displaystyle {\mathrm{}}^{}}$( 1.${\displaystyle {276}^{}}$ ${\displaystyle {}^{}}$ $){\displaystyle$ O $({1.276}^{n}}}$ 입니다$.$^[12]

기타 속성

n-vertex 입방형 그래프의 경로 폭은 최대 n/6이다.입방 그래프의 경로 너비에서 가장 잘 알려진 하한은 0.082n이다.이 하한과 n/6 상한 사이의 차이를 어떻게 줄일 것인지는 알려져 있지 않다.^[13]

이는 1736년 레온하르트 오일러에 의해 그래프 이론에 관한 첫 논문의 일부로 증명된 악수하는 보조정리기로서, 모든 입방형 그래프에는 정점 수가 짝수라는 것을 따른다.

피터슨의 정리에는 모든 무입방 브리지 그래프가 완벽하게 일치한다고 되어 있다.^[14]로바스와 플럼머는 모든 입방체 브리지가 없는 그래프에는 기하급수적인 수의 완벽한 일치가 있다고 추측했다.정점이 n개 있는 모든 입방체 브리지가 없는 그래프에는 최소 2개의^n/3656 완벽한 일치가 있다는 것을 보여주는 추측이 최근에 증명되었다.^[15]

알고리즘 및 복잡성

몇몇 연구자들은 기하급수적인 시간 알고리즘의 복잡성을 입방 그래프로 제한했다.예를 들어, 그래프의 경로 분해에 동적 프로그래밍을 적용함으로써, 포민과 호위는 시간 2에서^{n/6 + o(n)} 최대 독립 집합을 찾는 방법을 보여주었다.^[13]큐빅 그래프의 여행 세일즈맨 문제는 시간 O(1.2312ⁿ)와 다항식 공간에서 해결할 수 있다.^[16][17]

몇 가지 중요한 그래프 최적화 문제는 APX 하드인데, 이는 근사 비율이 상수에 의해 제한되는 근사 알고리즘을 가지고 있지만 P=NP가 아닌 한 근사 비율이 1인 다항 시간 근사 체계를 가지고 있지 않다는 것을 의미한다.여기에는 최소 꼭지점 커버, 최대 독립 세트, 최소 지배 세트 및 최대 컷을 찾는 문제가 포함된다.^[18]입방 그래프의 교차 번호(그래프 도면에서 교차하는 최소 가장자리 수)도 입방 그래프의 경우 NP-hard이지만 근사치일 수 있다.^[19]입방형 그래프의 이동 판매원 문제는 1153/1152 미만의 요인 내에서 NP에 가까운 것으로 입증되었다.^[20]

참고 항목

위키미디어 커먼즈에는 3-정규 그래프와 관련된 미디어가 있다.

• 단순 입방 그래프 표

참조

외부 링크

• Royle, Gordon. "Cubic symmetric graphs (The Foster Census)". Archived from the original on 2011-10-23.
• Weisstein, Eric W. "Bicubic Graph". MathWorld.
• Weisstein, Eric W. "Cubic Graph". MathWorld.