• 그래프
  • 단순 경로 vs 기본 경로
    • 단순 경로: 연결선을 두 번 포함하지 않는 경로
    • 기본 경로: 정점들이 두 번 만나지 않는 경로
  • 사이클: 종점 = 시점
    • 단순 사이클: 연결선이 반복되지 않는 사이클
    • 기본 사이클: 정점 반복하지 않는 사이클 (시작점 제외)
  • 연결 그래프: 모든 정점이 연결되어 있는 그래프
    • 연결 요소: 그래프에서 단절된 단위대로 끊어서 확인
    • 연결 수: 연결 요소의 개수
  • 멀티 그래프: 중복된 연결선 허용
  • 오일러 경로: 각 연결선을 단 한 번씩만 통과하는 경로
    • 오일러 경로가 될 조건: 경로의 양 끝 정점의 차수만 홀수거나 모든 정점의 차수가 짝수일 때
  • 오일러 순회: 정점 여러번 지나는 거 가능, 연결선 단 한 번씩만 통과하는 순회
    • 오일러 순회가 될 조건: 모든 정점의 차수가 짝수일 때 → 한붓그리기
  • 그래프에서 모든 정점의 차수 합 = 연결선 x 2
  • 해밀턴 경로: 모든 정점 한 번씩 지나지만 시작점으로 돌아오지 않음
  • 해밀턴 순회: 그래프에서 모든 정점들을 오직 한 번씩만 지나는 순회
    • 차수가 1인 점이 있을 때 → 해밀턴 순회 없음
    • 정점이 3개 이상인 단순 그래프에서 u, v의 차수의 합이 정점 개수보다 크면 해밀턴 순회를 가진다 → 해밀턴 순회가 무조건 이걸 만족하진 않음
  • 두 그래프가 동형이면?
    • 정점 개수 같음
    • 모서리 개수 같음 (?)
    • 각 대응하는 점의 차수가 같다
  • 평면 그래프: 각 연결선이 서로 교차하지 않는 그래프
    • 오일러의 정리
      • 정점의 수: v, 연결선의 수: e, 면의 수: f
      • v - e + f = 2
      • 평면 개수 셀 때 그래프 바깥에 있는 평면도 세어야 함
  • 완전 그래프: 각 정점이 모든 정점이랑 연결되는 그래프
    • 완전 그래프의 연결선 개수 → n(n-1)/2 개
  • k차 정규 그래프: 모든 정점의 차수가 k개일 때
  • 이분 그래프: 두 부류로 나눠서 X → Y 로 연결선이 이루어진 그래프 (like 함수)
    • 완전 이분 그래프: 전단사 함수(?)

소감

이산수학에서 그래프를 공부하며, 일상 속 관계와 연결을 수학적으로 표현하는 방법을 이해할 수 있어 흥미로웠습니다. 특히 그래프 이론이 네트워크, 경로 탐색 등 실생활 문제 해결에 널리 활용된다는 점이 인상적이었습니다. 앞으로도 그래프 이론을 통해 다양한 문제를 분석하고 해결할 수 있는 역량을 키우고 싶다는 의지가 생겼습니다.