경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요![[분류:그래프 이론]] '''평면그래프'''(planar graph)는 '''평면 매장'''(plane embedding, plane graph)이 존재하는 그래프를 말한다. 평면 매장은 평면 <math>\mathbb R^2</math>에 변끼리 겹치지 않게 그려진 그래프이며, 평면그래프는 평면 매장과 동형(isomorphic)인 그래프를 말한다. 평면에 그려졌으므로 그래프의 면을 가장 바깥에 있는 면인 '''무계 면'''/'''무한 면'''/'''외면'''(unbounded/infinite/external, outer face)과 외면이 아닌 '''유계 면'''/'''유한 면'''/'''내면'''(bounded/finite/inner face)으로 나눌 수 있다. 또한 평면과 [[곡면 종수]](genus)가 같은 모든 곡면에 매장가능함은 평면그래프임과 동치이다. == 쿠라토프스키 정리와 바그너 정리 == 평면그래프의 필요충분조건을 가장 간단하게 설명하는 정리이다. [[쿠라토프스키 정리]]에 따르면, [[그래프 (그래프 이론)|그래프]] <math>G</math>가 평면그래프일 필요충분조건은 <math>G</math>가 <math>K_5</math>나 <math>K_{3,3}</math>의 세분할(subdivision)과 동형(isomorphic)인 부분그래프를 갖지 않는 것이다. 즉 <math>K_5</math>나 <math>K_{3,3}</math>을 [[위상적 마이너]]로서 갖지 않는 것이다. 이와 비슷하게, [[바그너 정리]]는 그래프 <math>G</math>가 평면그래프일 필요충분조건은 <math>G</math>가 <math>K_5</math>나 <math>K_{3,3}</math>를 [[마이너]]<!--[[마이너 (그래프 이론)|마이너]]-->로서 갖지 않는 것이다. == 오일러 다면체 정리 == [[오일러 다면체 정리]](Euler's polyhedral theorem)는 [[연결 (그래프 이론)|연결]]된 평면그래프 <math>G</math>의 [[오일러 표수]] <math>\chi_E(G) = v-e+f </math>가 항상 2임을 말한다. 예를 들어, 삼각형 <math>K_3</math>의 경우엔 <math>v=3,~e=3,~f=2</math> (내면과 외면)이므로 <math>v-e+f =2</math>가 성립한다. 하지만 연결되지 않은 평면그래프에서는 당연하게도 성립하지 않는다. 다만 이때는 <math>v - e + f \ge 2</math>가 성립하게 된다. (연결되도록 변을 더 그려넣으면, <math>e</math>가 증가하여 <math>\chi_E(G) = 2</math>가 될 것이다. 따라서 <math>e</math>가 더 작다면 오일러 표수는 2 이상이 될 것이다.) 오일러 표수를 이용하면 변의 수와 꼭짓점의 수 사이의 부등식을 찾을 수 있다. 먼저, 그래프의 [[안둘레]](girth) <math>g</math>를 최소 [[순환 (그래프 이론)|순환]] 길이라고 정의하자. (없으면 무한대.) 예를 들어 [[고리 (그래프 이론)|고리]]가 있는 그래프는 안둘레가 1이고, [[단순그래프]]는 안둘레가 3 이상이다. 만약 순환이 없다면, 즉 안둘레가 무한대이면, 그 그래프는 [[나무 (그래프 이론)|나무]]이고 즉 <math>v=e+1,~f=1</math>임을 한다. 이제 안둘레가 <math>3\le g < \infty</math>라고 가정하자. 그러면 (한 면, 그 면과 인접한 변)의 순서쌍의 개수는 최대 <math>2e</math> 개이며(한 변은 최대 두 개의 면과 만난다), 최소 <math>gf</math> 개이다(한 면에는 <math>g</math> 개 이상의 인접한 변이 있다). 따라서 <math>2e \ge gf</math>이며, 오일러 다면체 정리에 의하여 :<math>\displaystyle 2=v-e+f \le v-e+\frac 2 g e = v - \frac{g-2}{g} e \implies e \le \frac g {g-2} (v-2)</math> 이 됨을 알 수 있다. 예를 들어 단순 평면그래프는 <math>e\le 3v-6</math>을 만족하며, 삼각형이 없는 단순그래프나 [[이분그래프]] 같은 경우에는 안둘레가 4 이상이므로 <math>e\le 2v - 4</math>이다. 이를 이용하면 평균 차수가 :<math>\displaystyle \operatorname{deg}(G) = \frac 1 v \sum_{x \in V(G)} \operatorname{deg}_G(x) = \frac{2e}{v} \le \frac{2g}{g-2} \frac{v-2}v < \frac{2g}{g-2}</math> 이므로, 차수가 <math>\frac{2g}{g-2}</math>보다 작은 꼭짓점이 반드시 존재하게 된다. 이는 [[그래프 채색]] 관련 문제를 다룰 때 유용하게 사용된다. == 동전 그래프 == == 쌍대 그래프와 매트로이드 == == 사색 정리, 오색 정리와 그래프 채색 == == 토마슨 정리와 리스트 채색 == == 평면그래프의 채색과 비영 흐름 == == 관련 정리와 추측 == 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț