둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
페미위키:포크 프로젝트/리브레 위키/그래프 (그래프 이론) 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
페미위키:포크 프로젝트/리브레 위키/그래프 (그래프 이론)
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
== 정의 == [[파일:defgraph.png|섬네일|다중 변과 고리를 가진 그래프]] '''그래프'''(graph)는 꼭짓점과 변으로 이루어져 있다. 자세히 말해, 순서쌍 <math>G=(V,E)</math>가 다음 두 조건 #<math>V</math>는 [[공집합]]이 아닌 유한집합이다. (이 조건은 논의의 편의를 위해 존재하며, 꼭짓점이 무한한 그래프를 다루기도 한다.) #<math>E</math>는 '끝점'이 정의되는 변들의 모임이다. 즉, <math>e\in E</math>에는 함수 <math>\partial:~e\mapsto \partial e</math>가 있어 <math>1\le |\partial e|\le 2</math>를 만족한다. 을 만족하면 <math>G</math>를 '''그래프'''라고 한다. 이때 <math>V</math>의 원소를 '''꼭짓점'''(vertex), <math>E</math>의 원소를 '''변'''(edge)이라고 한다. <math>\partial e = \partial f,~e\ne f</math>인 두 변은 '''다중 변'''(multiple edges) 또는 '''평행 변'''(parallel edges)라고 하며, 또 <math>|\partial e|=1</math>인 변을 '''고리'''(loop)라고 한다. 평행 변과 고리가 없는 그래프를 '''단순그래프'''(simple graph)라고 한다. 책에 따라, 단순그래프를 그래프라고 부르고, 평행 변과 고리를 허용하는 그래프를 '''다중그래프'''(multigraph)라고 하기도 한다. == 그래프 알고리즘 == * [[그래프 탐색]] * [[네트워크 플로우]] * [[최소비용 신장 트리]] * [[최단경로]] * 부그래프 ** [[클릭]] ** [[강연결요소]] == 그래프 색칠하기 == == 그래프의 종류 == * [[완전그래프]] * [[별그래프]] * [[순환그래프]] * [[바퀴그래프]] * [[사다리그래프]] * [[이분그래프]] ** [[완전이분그래프]] * [[평면그래프]] * [[나무 (그래프 이론)]] * [[정규그래프]] [[분류:그래프 이론]]
페미위키:포크 프로젝트/리브레 위키/그래프 (그래프 이론)
문서로 돌아갑니다.
다른 언어