그래프(Graph)

그래프(Graph)

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

 

그래프는 데이터 구조 의 한 형태로, 여러 개의 정점(node)과 이 정점들을 연결하는 간선(edge)으로 구성된다.

그래프는 데이터 간의 관계를 모델링하는데 사용될 수 있으며, 컴퓨터 과학, 네트워크 시스템, 사회학 등 다양한 분야에서 응용된다.

 

그래프의 유형

무방향 그래프(Undirected Graph)

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

 

무방향 그래프는 정점들이 방향없 없는 간선으로 연결된 그래프이다. 즉, 두 정점은 서로 연결되어 있고, 어느 쪽에서 출발해도 다른 쪽에 도달할 수 있다.

양방향이기 때문에 A와 B를 연결하는 간선이 있다면, A->B, B->A 둘 다 가능하다.

 

특징

• 대칭성 : 무방향 그래프의 간선은 대칭적이라 어느쪽에서든 이동할 수 있다.
• 루프 : 무방향 그래프에서는 한 정점에서 출발해 다른 정점으로 돌아오는 루프(loop)가 허용될 수 있으며, 두 정점 사이에 여러 개의 간선이 존재할 수 있는 다중 간선(multiple edges)도 허용될 수 있다.
• 인접성 : 두 정점이 간선으로 직접 연결되어 있을 경우, 서로 인접해 있다고 한다.

사용 예

사회 네트워크에서의 인간 관계, 도로망에서의 도로 시스템, 전기 회로에서의 연결 등 다양한 분야에서 활용된다.

인간 관계를 예로 들면, 두 사람이 서로 친구 관계라면 그 관계는 무방향 간선으로 표현될 수 있다.

 

표현 방법

• 무방향 그래프는 인접 리스트, 인접 행렬, 간선 리스트 등 다양한 방법으로 표현할 수 있는데, 각 방법은 그래프의 크기와 연산의 효율성 측에서 장단점을 가지고 있다
• 그 구조적 특성 때문에 알고리즘 문제해결, 네트워크 설계, 사회학 연구 등 다양한 분야에서 중요한 역할을 한다.

 

방향 그래프(Directed Graph)

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

 

방향 그래프는 정점들이 방향성을 가진 간선으로 연결된 그래프이다. 방향 그래프에서 간선은 (u, v)로 표현되며, u에서 v로의 방향성을 가진 연결을 나타낸다. 한 방향으로 연결되었기 때문에 v에서 u로 이동하려면 (v, u) 로 표현해야 한다.

 

특징

• 비대칭성 : 방향 그래프의 간선의 비대칭적이라 한 쪽 방향으로만 이동할 수 있다.
• 간선의 방향 : 모든 간선은 화살표로 표현되며, 이 화살표는 간선의 방향을 나타낸다.
• 루프와 다중 간선 : 방향 그래프에서도 루프와 다중 간선이 존재할 수 있다.
• 인접성 : 방향 그래프에서 정점 u가 v로의 간선을 가질 때, u는 v의 인접 정점이라고 한다. 하지만 v에서 u로의 간선이 없으면 그건 인접 정점이 아니다.

사용 예

웹 페이지 간의 링크 구조, 소프트웨어 패키지 의존성, 도시 간의 일방통행 도로망 등 다양한 분야에서 사용된다.

웹 페이지 A에서 다른 웹 페이지 B로의 하이퍼링크는 A->B로의 방향 간선으로 표현될 수 있다.

 

표현 방법

• 방향 그래프도 무방향 그래프처럼 인접 리스트, 인접 행렬, 간선 리스트 등의 방법으로 표현할 수 있으며, 각 방법은 그래프의 크기와 연산의 효율성 측면에서 장단점을 가진다.
• 그 구조적 특성 때문에 컴퓨터 과학, 통신 네트워크, 사회 과학 등 다양한 분야에서 중요한 역할을 한다.

 

가중치 그래프(Weighted Graph)

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

 

가중치 그래프는 그래프의 간선마다 가중치가 할당된 그래프를 의미한다. 가중치는 각 간선이 가지는 값으로, 두 정점을 연결하는 경로의 비용, 거리, 시간 등 다양한 수치를 나타낼 수 있다.

가중치 그래프는 무방향 가중치와 방향 가중치 그래프로 나뉠 수 있으며, 두 그래프에 가중치를 추가한 형태이다.

 

특징

• 가중치 : 각 간선에는 양이나 음의 가중치가 할당될 수 있다. 이 가중치는 그 간선을 통과하는데 드는 비용이나 거리 등을 나타낸다.
• 간선의 표현 : 가중치 그래프에서 간선은 일반적으로 (u, v, w) 형태로 표현되는데, u와 v는 간선, w는 간선의 가중치를 나타낸다.
• 응용 분야 : 가중치 그래프는 도로의 최단 경로 찾기, 네트워크 최적 경로 찾기 등 비용과 거리에 관한 분야에서 활용되며 그 외에도 다양하게 활용된다.

사용 예

• 최단 경로 문제 : 다익스트라, 벨만-포드, 플로이드-워셜 등의 알고리즘은 가중치 그래프의 한 정점에서 다른 정점까지의 최단 경로를 찾기 위해 사용된다.
• 최소 비용 신장 트리(MST) : 크루스칼 알고리즘, 프림 알고리즘 등은 가중치 그래프에서 모든 정점을 최소 비용으로 연결하는 트리를 찾는 데 사용된다.
• 네트워크 설계 : 도로망, 전력망 등의 설계에 있어 최소 비용으로 최대 효율을 달성하기 위해 사용된다.

 

표현 방법

• 가중치 그래프는 인접 리스트, 인접 행렬, 간선 리스트 등으로 표현할 수 있는데, 인접 행렬이나 리스트에서는 각 간선에 대한 가중치 정보를 함께 저장한다.
  • 예를 들어, 인접 리스트에서 각 리스트의 요소는 (u, w)의 형태로 구성될 수 있다.
• 가중치 그래프는 그래프의 기본적인 구조에 가중치라는 요소를 추가함으로써, 다양한 문제를 해결하는데 사용된다.

 

연결 그래프(Connected Graph) & 비연결 그래프(Disconnected Graph)

연결 그래프(Connected Graph)	비 연결 그래프(Disconnected Graph)

연결 그래프와 비연결 그래프는 그래프 이론에서 그래프의 연결성을 기준으로 구분되는 두 가지 주요 유형이다.

 

연결 그래프

연결 그래프는 무방향 그래프에서 어떤 두 정점 사이에도 경로가 존재하는 그래프를 말한다. 즉, 그래프의 모든 정점들이 서로 연결되어 있어서 어떤 정점에서 출발하더라도 다른 모든 정점으로 이동할 수 있는 그래프이다.

연결 그래프에서는 어떠한 정점도 고립되어있지 않으며, 모든 정점이 최소한 하나의 경로를 통해 서로 연결된다.

 

비연결 그래프

비연결 그래프는 무방향 그래프에서 최소 한 쌍의 정점 사이에 경로가 존재하지 않는 그래프를 의미한다. 다시 말해, 그래프 내에 적어도 하나의 정점이 다른 정점들과 연결되어 있지 않거나, 그래프가 두 개 이상의 서로 독립된 부분 그래프(Subgraph)로 나누어질 수 있는 경우를 말한다.

비연결 그래프에서는 한 부분 그래프의 정점에서 다른 부분 그래프의 정점으로 직접적인 경로를 통해 이동할 수 없다.

 

연결성의 중요성

• 그래프의 연결성은 네트워크 설계, 통신, 교통망 계획 등 다양한 분야에서 중요한 역할을 한다.
  • 예를 들어, 통신 네트워크에서는 모든 장치가 서로 통신할 수 있도록 하는 연결 그래프가 필수적이다.
• 반면, 비연결 그래프는 여러 독립된 시스템이나 네트워크의 구조를 모델링하는데 유용할 수 있다.

 

연결 그래프의 경우

• 강연결 그래프(Strongly Connected Graph) : 방향 그래프에서 모든 정점 쌍 사이에 양방향으로 경로가 존재할 경우
• 완전 그래프(Complete Graph) : 모든 정점이 서로 직접적으로 연결된 그래프로, 연결 그래프의 한 형태이다. 정점 수에 대해 가능한 모든 간선을 포함한 그래프

 

순환 그래프(Cyclic Graph) & 비순환 그래프(Acyclic Graph)

순환 그래프(Cyclic Graph)	비순환 그래프(Acyclic Graph)

순환 그래프와 비순환 그래프는 그래프의 구조적 특성에 따라 분류되는 두 가지 주요 유형이다.

 

순환 그래프

순환 그래프는 그래프 내에 적어도 하나 이상의 순환이 존재하는 그래프이다. 순환은 시작 정점과 끝 정점이 같은 경로로, 어떤 정점을 두 번 이상 방문하지 않고 해당 정점으로 돌아오는 경로를 의미한다.

순환 그래프는 무방향 그래프와 방향 그래프 모두에서 나타날 수 있다.

 

비순환 그래프

비순환 그래프는 그래프 내에 순환이 존재하지 않는 그래프이다. 즉, 어떠한 정점에서 출발해 같은 정점으로 돌아오는 경로가 존재하지 않는 그래프이다.

비순환 그래프는 특별한 유형으로 분류될 수 있다.

• 트리(Tree) : 비순환적이며 연결된 무방향 그래프이다. 모든 두 정점 사이에는 유일한 경로가 존재
• 방향 비순환 그래프(DAG) : 순환을 포함하지 않는 방향 그래프. 의존성 표현이나 데이터 처리 파이프라인 구성 등의 여러 분야에서 중요한 역할을 한다.

순환 그래프와 비순환 그래프의 중요성

• 순환 그래프
  • 순환은 네트워크 내에서 루프나 사이클을 나타내며, 이는 특정 자원이나 정보가 반복적으로 순환할 수 있음을 의미한다.
  • 예를 들어, 네트워크 설계에서 순환은 데이터 패킷이 무한히 순환하는 원인이 될 수 있다.
• 비순환 그래프
  • 특히, 방향 비순환 그래프(DAG)는 작업 스케줄링, 데이터베이스 설계, 프로젝트 관리 등에서 의존성 구조를 모델링하는데 유용하다.
  • 예를 들어, 어떤 작업이 다른 작업들이 완료된 후에만 시작될 수 있을 때, DAG를 사용해 이러한 의존성 관계를 표현할 수 있다.

 

완전 그래프(Complete Graph)

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

 

완전 그래프는 그래프 이론에서 모든 정점이 서로 직접 연결된 그래프를 의미한다.

완전 그래프는 그래프 내의 모든 정점 쌍 사이에 간선이 하나씩 있는 경우로 정의되며, 이러한 특성 때문에 완전 그래프는 매우 밀집된 연결 구조를 가지고 있다.

 

특징

• 간선의 수 : 완전 그래프에서는 모든 정점 쌍이 연결되어 있기 때문에, n개의 정점을 가진 완전 그래프의 간선의 수는 방향 그래프에서 n(n-1)/2, 무방향 그래프에서 n(n-1)이다.
• 정규성 : 완전 그래프는 정규 그래프의 한 예시이며, 정규 그래프란 모든 정점의 차수가 동일한 그래프를 말한다. 완전 그래프에서 각 정점의 차수를 (n - 1)이다.
• 단순 그래프 : 완전 그래프는 자기 자신으로의 간선이나 다중 간선을 가지지 않는 단순 그래프이다.

 

활용

완전 그래프는 이론적 연구와 알고리즘 설계에서 중요한 역할을 한다. 예를 들어, 완전 그래프는 네트워크 설계, 최적 경로 찾기, 그래프 색칠 문제 등 다양한 증명과 알고리즘에 활용된다.

완전 그래프는 그래프의 구조적 극단을 나타내며, 이를 통해 다양한 그래프 이론의 속성과 알고리즘의 성능을 분석할 수 있다.