그래프(Grape)

- 그래프 G는 집합 V와 정점 사이의 관계를 나타내는 연결선의 집합 E로 구성된다. 여기서 그래프의 두 집합 정점과 간선은 유한하다고 가정하며, G = (V, E)로 표기한다.

- 정점(Vertex) V는 공집합이 아닌 정점들의 유한 집합이다.

- 간선(Edge) E는 공집합도 허용하는 간선들의 유한 집합이다.(정점들의 쌍으로 표현)

- 정점의 차수는 그 정점에 부수(incident)된 간선들의 수이다.

- 위상순서, 최단경로, 작업 네트워크 등에 이용한다.

- 임의의 유한집합 S에 대한 이항관계(Binary Relation)는 무방향 그래프 혹은 방향 그래프로 나타낼 수 있다.

- 그래프를 인접행렬로 표현했을 때 무방향 그래프는 반드시 대칭인 반면, 방향 그래프에서는 대칭이 아닐 수도 있다.

 

무방향 그래프

- 무방향 그래프는 두 정점을 잇는 간선에 순서가 없다. 즉, (v1, v2) = (v2, v1)이다.

- 정점 v1에서 v2로 가는 방향이 표시되지 않은 그래프로, 양방향 관계가 성립한다.

- 무방향 그래프에서 모든 정점의 차수의 합은 간선의 수에 2를 곱한 것과 같다.

- n개의 정점으로 구성된 무방향 그래프에서 최대 간선 수 : n*(n+1)/2

 

방향그래프

- 방향 그래프는 다이그래프(digraph)라고도 하며, 한 정점 v1에서 v2로 가는 방향이 표시된 그래프로 <v1, v2> != <v2, v1>이다.

- 간선 <v1, v2>는 v1->v2로 표시하고 v1을 간선의 Tail, v2를 간선의 Head라고 한다.

- n개의 정점으로 구성된 방향그래프에서 최대 간선 수 : n(n-1)

- 방향 그래프의 간선을 아크(Arc)라고 한다.

 

종류

완전 그래프

- 모든 정점(Vertex)이 간선으로 서로 연결된 그래프로서, 모든 정점의 차수는 같다.

- 최대 간선 수를 가지는 그래프이다.

- 무방향 그래프가 완전 그래프인 경우 간선의 수는 항상 n(n-1)/2이다.

- 방향 그래프가 완전 그래프인 경우 간선의 수는 항상 n(n-1)이다.

 

부분 그래프

- G2는 G1의 부분 그래프이다.

- 말 그대로 한 그래프의 부분을 나타내는 그래프이다.

 

그래프의 표현

인접 행렬

인접 리스트

관련 백준 문제 - 5567번(www.acmicpc.net/problem/5567)

package com.as0220;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class n5567_wedding {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());

		int[][] friend = new int[N][N];
		boolean[] check = new boolean[N];

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int f1 = Integer.parseInt(st.nextToken());
			int f2 = Integer.parseInt(st.nextToken());
			friend[f1 - 1][f2 - 1] = 1;
			friend[f2 - 1][f1 - 1] = 1;
		}

		int cnt = 0;
		for (int i = 1; i < N; i++) {
			if(friend[0][i] == 1) {
				if(!check[i]) {
					cnt++;
					check[i] = true;
				}
				for(int j = 1; j <N; j++) {
					if(friend[i][j] == 1 && !check[j]) {
						cnt++;
						check[j] = true;
					}
				}
			}
		}
		System.out.println(cnt);
	}
}