완전 이분 그래프
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
완전 이분 그래프는 정점을 두 개의 부분 집합으로 분할할 수 있으며, 동일한 부분 집합 내에 변이 없고, 서로 다른 부분 집합의 정점을 연결하는 모든 변을 포함하는 그래프이다. 완전 이분 그래프는 k분 그래프이며 채색수는 k 이하이다. 완전 이분 그래프는 Km,n으로 표기하며, 평면 그래프가 K3,3을 그래프 마이너로 가질 수 없다는 성질을 갖는다.
집합 의 조각 분할
2. 정의
:
이 주어졌을 때, 이 분할에 대응하는 '''완전 분 그래프'''(complete -partite graph영어)는 위와 같은 분할에 대하여 분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.
:4. 예
5. 역사
아타나시우스 키르허가 1669년에 완전 이분 그래프의 그림을 출판하였다.[16]
6. 응용
완전 이분 그래프는 여러 분야에서 응용된다.
형식 개념 분석에서 관계의 방향 그래프의 부분 그래프로 발견되는 최대 이분 그래프는 '개념'이라고 불린다. 이러한 부분 그래프를 통해 형식 개념 분석을 할 수 있다.[6]
또한, 주어진 이분 그래프에서 완전 이분 부분 그래프를 찾는 문제는 NP-완전 문제이다.[8]
6. 1. 형식 개념 분석
관계의 방향 그래프의 부분 그래프로 발견되는 최대 이분 그래프는 '개념'이라고 불린다. 이러한 부분 그래프의 만남과 결합을 통해 격자가 형성될 때, 관계는 유도된 개념 격자를 갖는다. 이러한 유형의 관계 분석을 형식 개념 분석이라고 한다.[6]6. 2. NP-완전 문제
주어진 이분 그래프에서 완전 이분 부분 그래프를 찾는 문제는 NP-완전 문제이다.[8] 매개변수 ''i''가 주어졌을 때, 이분 그래프가참조
[1]
서적
Graph Theory with Applications
https://archive.org/[...]
North-Holland
[2]
서적
Graph Theory
http://diestel-graph[...]
Springer
[3]
서적
An Atlas of Graphs
Clarendon Press
[4]
서적
Combinatorics: Ancient and Modern
Oxford University Press
[5]
서적
Matching theory
https://books.google[...]
AMS Chelsea
[6]
서적
A Logical Approach to Discrete Math
https://books.google[...]
Springer
[7]
서적
Regular Complex Polytopes
[8]
서적
Computers and Intractability: A Guide to the Theory of NP-Completeness
W. H. Freeman
[9]
서적
[10]
서적
Algebraic Graph Theory
https://books.google[...]
Cambridge University Press
[11]
서적
Modern Graph Theory
https://books.google[...]
Springer
[12]
서적
[13]
서적
Graphs, Networks and Algorithms
https://books.google[...]
Springer
[14]
서적
Graph Coloring Problems
https://books.google[...]
Wiley
[15]
간행물
Absolute retracts of bipartite graphs
[16]
서적
Oxford University Press
2013
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com