1강. 그래프 이론 기초
1. 그래프란 무엇인고, 왜 중요할까?
(1) 그래프 정의
•
정점 집합과 간선 집합으로 이루어진 수학적 구조
•
하나의 간선은 두 개의 정점을 연결
•
모든 정점의 쌍이 반드시 간선으로 연결되는 것은 아님
그래프 = 네트워크
정점 = 노드
간선 = 엣지 or 링크
(2) 그래프의 중요성
•
우리 주변에는 많은 복잡계가 존재 → 그래프를 통해 효과적으로 표현 가능
•
복잡계를 이해하고 복잡계에 대한 정확한 예측을 하기 위해서는 복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요함
(3) 그래프 관련 인공지능 문제
•
정점 분류 문제 : 트위터에서 공유 관계를 분석하여 각 사용자의 정치적 성향 파악 or 단백질의 상호작용을 분석하여 단백질의 역할
•
연결 예측 문제 : 페이스북 소셜네트워크 진화
•
추천 문제
•
군집 분석 문제
•
랭킹 및 정보 검색 문제
•
정보 전파 및 바이럴 마케팅 문제
2. 그래프 관련 필수 기초 개념
(1) 그래프의 유형 및 분류
•
간선에 방향이 없는 그래프
•
간선에 방향이 있는 그래프
•
간선에 가중치가 없는 그래프
•
간선에 가중치가 있는 그래프
•
동종 그래프 : 단일 종류의 정점
•
이종 그래프 : 두 종류의 정점
(2) 필수 기초 개념
•
정점들의 집합 : V
•
간선들의 집합 : E
•
그래프 : G=(V,E)
•
정점의 이웃 : 정점과 연결된 다른 정점
ㅇ
