광주과학기술원

Graph Theory
Prufer code에 대하여
u는 독일어 움라우트 표기해야한다.prufer code는 트리구조를 인코딩하는 방법으로 n개 정점을 가진 트리를 n-2개 정수로 표현한다.트리로부터 프뤼퍼코드를 생성하거나 프뤼버코드로부터 트리를 생성하는 예제는 2024 그래프이론 퀴즈와 중간고사 모두에서 출제되었으므로 후배님들은 확인해보길바란다. 그냥 공부했던 내용을 기록하기 위해 붙여둔다.
→2024.12.28
Graph Theory
Identify the vertices of a Petersen graph in your drawing and explainwhy. (Note again that the vertex set of the Petersen graph is the collec-tion of 2-subsets of [5], for example, 13 means {1, 3}. Two vertices aband cd are adjacent iff {a, b} ∩ {c, d} =∅
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 2SolutionThe set ([5] = \{1, 2, 3, 4, 5\}) has the following 2-subsets:[12, 13, 14, 15, 23, 24, 25, 34, 35, 45.]These 10 subsets form the 10 vertices of the Peterson graph.To determine adjacency, the rule is:Two vertices (ab) and (cd) are adjacent if and only if (\{a, b\} \cap \{c, d\} =∅).Example:Vertex (34) is adjacent to (12), (25)..
→2024.12.28
Graph Theory
Let u and v be adjacent vertices in a simple graph G. Prove that uvbelongs to at least $$d(u) + d(v) - n(G)$$ triangles in G.
문제출처 - 광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 2Solution(i). Since $u$ and $v$ are adjacent, $uv$ is an edge in $G$.(ii). The number of triangles containing $uv$ is the same as the size of the intersection of $N(u)$ and $N(v)$. $N$ means neighbor.(iii). For example, if $N(u) = \{v, w_1, w_2, w_3\}$ and $N(v) = \{u, w_1, w_2\}$, then: $$N(u) \cap N(v) = \{w_1, w_2\}.$$ Thus, the t..
→2024.12.28

• 이전
• 1
• 다음