부분 그래프
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
부분 그래프는 주어진 그래프의 정점 집합과 변 집합의 부분집합으로 구성된 그래프이다. 그래프 G의 부분 그래프 H는 H의 정점 집합이 G의 정점 집합의 부분집합이고, H의 변 집합이 G의 변 집합의 부분집합일 때 정의된다. 부분 그래프, 유도 부분 그래프, 인자 간의 관계는 예시를 통해 설명된다.
더 읽어볼만한 페이지
- 그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다. - 그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
| 부분 그래프 | |
|---|---|
| 정의 | |
| 정의 | 그래프 이론에서, 그래프 H는 그래프 G의 부분 그래프임은 다음 조건을 만족한다. |
| 조건 | G의 모든 정점은 H의 정점이기도 하다. G의 모든 변은 H의 변이기도 하다. |
| 종류 | |
| 유도 부분 그래프 | G의 부분 그래프 H에서 H의 모든 변은 G의 변이기도 하면 H는 G의 유도 부분 그래프이다. |
| 스패닝 부분 그래프 | G의 부분 그래프 H에서 H의 모든 정점은 G의 정점이기도 하면 H는 G의 스패닝 부분 그래프이다. |
| 예시 | |
| 완전 그래프 K5 | [[파일:Clique_5_demo.svg|완전 그래프 K5]] |
| 부분 그래프 | [[파일:Clique_5_subgraph_demo.svg|부분 그래프]] |
| 유도 부분 그래프 | [[파일:Clique_5_induced_subgraph_demo.svg|유도 부분 그래프]] |
2. 정의
그래프 G의 부분 그래프 H는 G의 정점과 변의 일부를 포함하는 그래프이다. 부분 그래프에는 유도 부분 그래프, 인자 등의 개념이 있다.
2. 1. 부분 그래프 (Subgraph)
그래프 의 '''부분 그래프''' 는 다음을 만족시키는 그래프이다.2. 2. 유도 부분 그래프 (Induced Subgraph)
그래프 의 '''유도 부분 그래프'''(induced subgraph영어) 는 다음을 만족시키는 그래프이다.2. 3. 인자 (Factor)
그래프 G의 부분 그래프 가운데, G의 모든 꼭짓점을 포함하는 것을 '''인자'''(factor|팩터영어)라고 한다.3. 예시
다음 네 개의 그래프를 생각해 보자.
- ''G''1, ''G''2, ''G''3 모두 ''G''의 부분 그래프이다.
- ''G''1은 변 26과 변 67을 포함하지 않으므로 유도 부분 그래프가 아니다. 반면, ''G''2와 ''G''3는 유도 부분 그래프이다.
- ''G''3는 ''G''2의 유도 부분 그래프이다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com