학습개요
수학자 오일러(Euler)가 쾨니히스베르크 다리 문제를 해결하면서 사용한 그래프는 오늘날 가장 강력한 모델링 수단으로 세상의 많은 것들 특히 “관계”를 잘 표현합니다. 이 장은 먼저 그래프 개념을 소개하고 많은 용어를 정의합니다. 용어에 익숙해야 이어지는 내용을 잘 파악할 수 있습니다.
특히 그래프를 수학의 집합 즉 G=(V,E)로 정의하는 것을 잘 이해해야 합니다. 그리고 그래프를 컴퓨터로 다루기 위한 추상 자료형을 소개합니다. 그래프로 실세계 문제를 표현하고 컴퓨터로 처리하기 위해서는 어떤 기능들이 제공되어야 하는지 잘 이해해야합니다. 다음으로 그래프를 표현한 여러 가지 방법을 소개합니다. 우리가 흔히 그림으로 그려내는 그래프는 컴퓨터 내부에 인접행렬 혹은 인접 리스트로 표현하여 저장합니다. 이 장과 마지막인 14장에서는 그래프를 상세하게 다루어 보겠습니다.
학습목표
- 대상들의 관계를 그래프로 나타낼 수 있다.
- 그래프와 관련한 여러 용어를 구분하고 정확하게 설명할 수 있다.
- 추상 자료형으로써 그래프가 가져야할 기능을 설명할 수 있다.
- 그래프를 컴퓨터 내부에 표현하는 방법을 설명할 수 있다.
연습문제
- 다음 중 설명이 틀린 것은 무엇인가 ?
- 루프 : 한 정점에서 출발하여 자신으로 연결하는 간선
- 사이클 : 시작점과 끝점이 같은 경로
- 간선 : 그래프에 있는 대상들의 관계
- 인접 리스트 : 그래프를 구성하는 행렬
–
은 무엇을 나타내기 위한 방법인가 ?
- 트리의 행렬 표현
- 그래프의 리스트 표현
- 그래프의 인접 행렬 표현
- 희소행렬의 표현
–
- 다음 설명으로 틀린 것은 무엇인가 ?
- 정점 집합 V와 간선 집합 E에 대하여 그래프는 G=(V,E)입니다.
- 방향 그래프는 간선의 방향이 유의미한 그래프로 예를 들어 부자 관계를 그래프로 나타내면 간선은 유의미 합니다.
- 두 정점쌍이 간선을 여러 개 가질 수 있는 그래프를 다면 그래프라 합니다.
- 두 정점이 간선으로 연결되었을 때 두 정정이 인접한다고 표현합니다.
정리하기
- 정점 집합 V와 간선 집합 E에 대하여 그래프는 G=(V,E)입니다. 즉, 대상(V)과 그 대상들의 관계(E)를 나타내는 수단입니다.
- 방향 그래프는 간선의 방향이 유의미한 그래프로 예를 들어 부자 관계를 그래프로 나타내면 간선은 유의미 합니다.
- 무방향 그래프는 간선의 방향이 무의미한 그래프로 예를 들어 두 지점 사이에 도로가 있는 지 아닌지를 그래프로 나타내면 간선은 무의미합니다. 단, 도로가 일방통행로라면 간선의 방향은 의미를 갖고 그 그래프는 방향 그래프로 나타내야 합니다.
- 두 정점쌍이 간선을 여러 개 가질 수 있는 그래프를 다중 그래프라 합니다. 예를 들어 두 지점사이에 여러 교통수단이 있다면 다중 그래프로 나타 낼 수 있습니다.
- 두 정점을 잇는 간선이 중요도나 비용 등을 나타내는 가중 값을 갖는 그래프를 가중 그래프라고 합니다. 예를 들어 두 지점 사이를 연결 하는 도로의 거리가 중요한 의미를 갖는 문제라면 그 그래프는 가중 그래프로 표현해야 합니다.
- 두 정점을 잇는 간선 열을 경로라 합니다. 그리고 경로에 있는 간선의 수를 그 경로의 경로 길이로 정의합니다.
- 한 정점에서 출발하여 자신으로 연결하는 간선을 루프라고 합니다. 예를 들어 입력에 따라 상태가 변하는 시스템을 그래프로 나타내는 경우 어떤 입력에 대해서는 상태가 변하지 않는다면 루프로 표현할 수 있습니다.
- 시작점과 끝점이 같은 경로를 사이클이라 합니다. 그리고 하나 이상의 사이클을 갖는 그래프를 사이클이 있는 그래프 혹은 사이클 그래프라 하고 사이클이 없는 그래프를 무 사이클 그래프 혹은 트리라고 합니다.
- 두 정점이 간선으로 연결되었을 때 두 정정이 인접한다고 표현합니다. 두 정점이 잇는 경로가 있다는 것과 반드시 구분해야 합니다.
- 그래프의 표현방법의 하나로 정점 사이의 인접성을 행렬로 나타낸 것을 인접행렬 표현법이라 하고 정점 사이의 인접성을 연결 리스트로 나타낸 것을 인접 리스트 표현법이라 합니다. 그래프가 정점 개수에 비하여 간선 개수가 적으면 연결 리스트로 나타내야 기억 장소를 효율적으로 사용할 수 있습니다.