MMSS 3일차 (7/25 Tue)

---

key: jekyll-text-theme title: MMSS 3일차 (7/25 Tue) excerpt: 쌩그래프이론 vs 그래프자료구조 tags: [travel, mmss] key: 230726 —

• Null graph: No vertices
• Complement of a graph : Same vertex as the original graph, inverted edges from the original graph
• Independent Set : A set of vertices in a graph with no edges
• Walk : Moving around a graph
• Trail : Walk without repeating edges
• Path : Walk without repeating vertices
• Cycle : A path where the start and end vertices are the same

• Eulerian Graph : A connected graph with a closed Eulerian trail

• 명제 : 역, 대우, 귀류법, 수학적 귀납법, 필요조건 및 충분조건에 대해 배웠다. 한국과 달리 미국에서는 이러한 명제나 논리적 관계, 증명에 대해서 배우는 것이 아예 없다고 한다.
• 수학적 귀납법을 이용하여 convex n-gon을 n-2개의 삼각형으로 분할하는 것이 가능하다는 것을 증명하였다.
• Complement : 그래프의 Complement에 대해 배우면서, 그래프가 연결되어 있지 않다면 그 complement는 연결되어 있음을 증명하였다.
• Eulerian : 그래프의 Eulerian trail과 Eulerian graph에 대해 배우고, 그래프가 Eulerian인 것의 필요충분조건이 모든 차수가 짝수인 연결 그래프일 것이라는 사실을 증명하였다.
• self-complementary한 그래프 몇 가지를 찾아보고, order n의 self-complementary한 그래프가 주어질 때 order n+4인 self-complementary 그래프를 항상 만들 수 있음을 증명하였다.
  • Self-complementary : 그래프와 그래프의 Complement 그래프가 서로 동형일 경우 그래프가 Self-complementary하다고 한다.
• 기타 삼분 그래프, Knight graph, 차수 개수에 제한이 있는 그래프에서의 사이클 등 여러 가지 문제를 해결하였다.

그 외

• 확실히 그래프 그 자체에 대해 더 공부하다 보니까 재미있습니다.
• 타겟에 다녀왔습니다. 17년도 이후로 5.5년만에 다녀온 타겟입니다. 두 타겟 사이에 거리가 좀 있다 보니(15000km?) 타겟 내에서 파는 것도 많이 다른 것 같다는 느낌도 듭니다.
• 확실히 대학과 도시가 섞여 있다는 게 느껴집니다. 근데 학교가 너무 커져서 오히려 별로 안 좋은 것 같기도 한 게, 기숙사에서 Dept. of Math 건물까지 걸어서 10~12분 정도 갑니다.