둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
그래프 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
그래프
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
== 개요 == 그래프는 점(Vertex)과 이음선(Edge)으로 이루어진 수학적 구조이다. 이를 형식화하면 다음과 같이 표현할 수 있다. * G = (V, E) * V = {v<sub>1</sub>, v<sub>2</sub>, v<sub>3</sub>, ... , v<sub>n</sub>} * E = {(v<sub>i</sub>, v<sub>j</sub>), ... } 즉, 그래프는 점 집합과 이음선 집합의 순서쌍이다. 이음선 집합의 이음선은 V<sup>2</sup>의 부분집합이다. V<sup>2</sup>, 즉 V×V는 집합론에서 [[교차곱]](Cross Product) 또는 데카르트곱(Cartesian Product)이라고 불리는 연산의 결과물이다. 위와 같이 집합론의 기호들을 사용하여 표현된 그래프는 비교적 쉽게 행렬 표기로 바꿀 수 있다. 예를 들어, v<sub>i</sub>와 v<sub>j</sub>가 서로 연결되어 있을 경우, 그래프를 나타내는 행렬 G의 원소 G[i][j]는 1이며, 연결되어 있지 않을 경우 0이다. == 특수한 그래프 == 용도에 따라 방향 있는 그래프(directed graph)와 가중치 있는 그래프(weighted graph)를 정의하여 사용한다. 위의 그래프 G를 의미하는 행렬을 예로 들면, 방향 있는 그래프는 대칭행렬이 아닐 수 있다. 즉, G[i][j]≠G[j][i]일 수 있다. 반면 방향 없는 그래프는 필연적으로 대칭행렬이다. 가중치 있는 그래프는 이음선이 특수한 속성을 가질 때 이용한다. 이 경우, 그래프 G를 나타내는 행렬의 각 원소는 점들 사이의 이어짐 여부를 나타냄과 동시에, 각 이음선에 가해진 가중치를 나타낸다. 따라서 행렬 G는 가중치 행렬(weight matrix)이라고 할 수 있다. 또한, 그래프의 이음선들 사이의 순환(recursion)이 없으면서 모든 점이 하나 이상의 이음선과 연결된 특수한 경우를 트리(Tree)라고 부른다. 학부 과정을 기준으로 볼 때, 단언컨대 트리는 자료구조의 꽃이다. == 용도 == 가중치 있는 그래프의 기초적인 여러 활용방식이 있다. 이 활용방식들은 아주 실용적이다. 예를 들어, 최소비용신장트리(minimum spanning tree) 알고리즘과 최단경로 찾기(shortest path) 알고리즘은 계산 시간을 획기적으로 줄여주는 아주 고마운 알고리즘일 뿐만 아니라, 시험에도 자주 출제되는 단골 문제이다. [[점근상한]]표기법 O(n)이 요구되는 순차검색 알고리즘을, 그래프 개념을 이용한 비교 기반 정렬 알고리즘을 채택하여 O(n·log(n))시간만에 정렬한 후, 이진검색 알고리즘을 이용하여 검색시간을 O(log(n))으로 단축시킬 수 있다. 그러나 정렬되지 않은 데이터는 이진검색을 사용할 수 없다.
그래프
문서로 돌아갑니다.
다른 언어