검색 결과

[[그래프 이론]]에서 '''완전 그래프'''(完全graph, {{llang|en|complete graph}})는 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그 (단순) [[그래프]]의 범주 <math>\operatorname{Graph}</math> 위에, 그래프를 그 꼭짓점 집합으로 대응시키는 망각 [[함자 ( ...

...g|en|planar graph}})는 평면 상에 [[그래프]]를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 [[그래프]]를 의미한다. 파일:Complete graph K5.svg|꼭짓점이 5개인 [[완전 그래프]](<math>K_5</math>) ...

'''슈니더의 정리'''(Schnyder's theorem, -定理)은 [[그래프 이론]]의 [[정리]]로, [[평면 그래프]]의 특성화를 위한 조건을 제공한다. [[그래프]] <math>G</math>에 대하여, '''인접 부분 순서 집합'''({{llang|en|incidence poset}}) <mat ...

[[그래프 이론]]에서 '''비징의 정리'''(Визинг의定理, {{llang|en|Vizing’s theorem}})는 [[그래프]]의 [[변 색칠수]]와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다. '''비징의 정리'''에 따르면, (단순 무향) 그래프 <math>\Gamma</math>의 변 색칠수 <math>\chi'(\Gamma)</math> 및 <math>\Gamma</math> ...

...만약 그래프에서 왼쪽 세 꼭짓점을 제외한 모든 꼭짓점을 지웠을 때 얻어지는 그래프(굵은 색)는 [[색칠수]]와 최대 [[클릭 (그래프 이론)|클릭]]의 크기가 같다. 다른 꼭짓점을 지웠을 때에도 마찬가지 결과가 얻어진다.]] ...{llang|en|perfect graph}})는 그 [[색칠수]]가 [[클릭 (그래프 이론)|클릭]]과 특별한 관계를 만족시키는 [[그래프]]이다. ...

...서로 겹치지 않는 두 집합 X와 Y의 [[합집합]]이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 [[이분 그래프]]이다. 가 주어졌다고 하자. 이 [[집합의 분할]]에 대응하는 '''완전 <math>k</math>분 그래프'''({{llang|en|complete <math>k</math>-partite graph}})는 위와 같은 분할에 대하여 <math ...

[[군론]]과 [[그래프 이론]]에서 '''케일리 그래프'''({{llang|en|Cayley graph}})는 군의 구조를 반영하는 [[그래프]]이다. ...ubset G</math>가 주어졌다고 하자. '''케일리 그래프''' <math>\Gamma(G,S)</math>는 다음과 같은 [[그래프]]이다. ...

{{다른 뜻 넘어옴|쾨니그 정리|무한 그래프에 대한 정리|쾨니그 보조정리}} {{다른 뜻 넘어옴|쾨니그 정리|[[기수 (수학)|기수]]에 대한 정리|쾨니그의 정리 (집합론)}} ...

...H''에 대해, ''G''의 임의의 두 꼭짓점 ''u''와 ''v''가 주어졌을 때 ''u''와 ''v''가 ''G''에서 [[그래프 이론 용어#무향 그래프의 기본 정의|인접]]인 것과 <math> f(u) </math>와 <math> f(v) </math>가 ''H''에서 두 그래프 ''G''와 ''H'' 간에 동형사상이 존재하면, 두 그래프는 '''동형'''(同型, [[영어]]: isomorphic)이라고 하고 < ...

...의 변들을 [[꼭짓점]]으로 삼고, 원래 그래프의 변의 인접 여부를 변으로 삼는 그래프이다. 끝을 선으로 연결한 그래프는 '''꺾은선 그래프'''라고 한다. ...단순) 그래프 <math>\Gamma</math>의 '''선 그래프''' <math>L(\Gamma)</math>는 다음과 같은 [[그래프]]이다. ...

[[그래프 이론]]에서 '''그래프 색칠'''(graph色漆, {{llang|en|graph colo(u)ring}})은 [[그래프]]의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다. (단순) 그래프 <math>G</math>의 '''색칠''' <math>(C,c)</math>은 집합 <math>C</math> 및 함수 <math>c ...

[[파일:Натурализация гамильтоновых циклов.jpg|섬네일|8*8 [[격자 그래프|그리드 그래프]]의 세 가지 예]] ...Hamilton經路, {{llang|en|Hamiltonian path}})는 모든 [[꼭짓점]]을 한 번씩 지나는 [[경로 (그래프 이론)|경로]]이다. ...

...etersen1_tiny.svg|섬네일|200x200픽셀| 고도로 대칭적인 그래프인 [[페테르센 그래프]]는 꼭지점 전이적, [[대칭 그래프|대칭]], 거리 전이적인 거리 정규 그래프이다. 페테르센 그래프의 [[지름]]은 2이다. 페테르센 그래프의 [[자기동형군]]에는 120 ...그래프 이론|알고리즘]]적인 접근 방식과 대조된다. 대수적 그래프 이론에는 [[선형대수학]], [[군론]]의 응용 및 [[그래프 속성|그래프 불변량]] 연구 등 세 가지 주요 갈래가 있다. ...

...화 이론]] 에서 '''최대 유량 최소 컷 정리'''는 [[네트워크 흐름]] 에서 [[그래프 이론 용어|''소스'']]에서 [[그래프 이론 용어|''싱크'']]로 전달되는 유량의 최대 값과 최소 컷에서 간선의 총 가중치가 같음을 의미한다. 이는 [[선형 계획법]]의 쌍대성 정리의 특별한 경우이며 [[멩거의 정리|Menger의 정리]] 와 [[쾨니그의 정리|König–Egerváry 정리를]] 유도하는 데 사용될 수 있다.<ref>{{저널 인용|제목=On the max-flow min-cu ...

[[파일:Complete-edge-coloring.svg|섬네일|오른쪽|[[완전 그래프]] <math>K_8</math>의 7색 변 색칠]] [[그래프 이론]]에서 '''변 색칠'''(邊色漆, {{llang|en|edge colo(u)ring}}은 [[그래프]]의 변들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다.<ref>{{서적 인용|제목=Graph edge coloring: Vi ...

[[파일:6n-graf.svg|섬네일|right|250px|6개의 꼭짓점과 7개의 변을 갖는 그래프]] ...래프는 [[꼭짓점]]과 이를 연결하는 [[그래프 이론 용어|변]]으로 구성된다. 두 점을 연결하는 변에 방향이 있는 그래프를 [[유향 그래프]]라 하며, 방향이 없는 무향 그래프와 구분된다. 그래프는 [[이산수학]]에서 다루는 주요 수학적 대상 중 하나이다. ...

...Ramsey’s theorem}})는 충분히 큰 [[완전 그래프]]의 변을 [[그래프 색칠|색칠]]할 경우, 동색의 [[클릭 (그래프 이론)|클릭]]을 찾을 수 있다는 정리이다. 가 주어졌다고 하자. '''램지의 정리'''에 따르면 다음 조건을 만족시키는 양의 정수 <math>R(n_1,\dots,n_m;c,m)</math>가 존재한다. ...

'''네른스트 열 정리'''(Nernst heat theorem)는 20세기 초 [[발터 네른스트]]에 의해서 만들어졌으며, [[열역학 제3법칙]]의 발달에 == 이론 == ...

...주어진 [[매트로이드]]에서 일부 [[원소 (수학)|원소]]를 “삭제”하거나, 일부 원소를 “축약”하여 얻어지는 매트로이드이다. [[그래프 마이너]]의 일반화이다. [[그래프 마이너]]는 매트로이드 마이너의 특수한 경우이다. 구체적으로, (유한 또는 무한) [[그래프]] <math>\Gamma</math>의 (유한형) [[순환 매트로이드]]를 <math>\operatorname M(\Gamma)</m ...

[[조합적 집합론]]에서 '''홀 결혼 정리'''(Hall結婚定理, {{llang|en|Hall marriage theorem}})는 여러 [[유한 집합]]들의 집합족으로부터, 각 [[집합족]] <math>\mathcal T</math>의 모든 원소가 [[유한 집합]]이라고 하자. '''홀 결혼 정리'''에 따르면, 다음 두 조건이 서로 동치이다.<ref name="윤영진"/>{{rp|289}} ...