분류 전체보기

Graph Theory
Prufer code에 대하여
u는 독일어 움라우트 표기해야한다.prufer code는 트리구조를 인코딩하는 방법으로 n개 정점을 가진 트리를 n-2개 정수로 표현한다.트리로부터 프뤼퍼코드를 생성하거나 프뤼버코드로부터 트리를 생성하는 예제는 2024 그래프이론 퀴즈와 중간고사 모두에서 출제되었으므로 후배님들은 확인해보길바란다. 그냥 공부했던 내용을 기록하기 위해 붙여둔다.
→2024.12.28
Graph Theory
Show konig thm implies Hall’s thm
교수님께서 몇번 강조를 하셔서 증명은 해봤는데, 2024 기준 시험이나 퀴즈에 출제된 바는 없습니다. SolutionHall's Theorem:For a bipartite graph $G = (X, Y, E)$, a perfect matching exists if and only if the following condition holds: $$\forall S \subseteq X, |N(S)| \geq |S|.$$ We need to show that $\alpha'(G) = \beta(G)$ for every bipartite $G$ implies Hall's theorem. Proof: Suppose the graph $G$ satisfies the condition of Hall's theor..
→2024.12.28
Graph Theory
For all positive integers r and d that satisfy r ≤ d ≤ 2r, construct a simple graphwith radius r and diameter d.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5 Solution(c) Construct a simple graph with radius $r$ and diameter $d$Construction: Consider the cycle $C_{2r}$ defined on $V = {0, 1, 2, \dots, 2r-1}$. In this case, we have: $$\text{rad}(C_{2r}) = r.$$ When $d = r$, the graph satisfies: $$\text{diam}(C_{2r}) = \text{rad}(C_{2r}) = r.$$ Now assume $2r \geq d > r$. Define a path $..
→2024.12.28
Graph Theory
Use part (a) to prove that diam(G) ≤ 2rad(G) for every graph G.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5풀이(a)는 삼각부등식. 이전 풀이 참고.Proof: If there is no path $a \dots b$ or path $b \dots c$, then $d(a, b)$ or $d(b, c) = \infty$, so the inequality is trivially satisfied. Otherwise, there exists a path $a \dots b$ of length $d(a, b)$ and a path $b \dots c$ of length $d(b, c)$. We may compose these two paths to form a longer walk $a \dots b ..
→2024.12.28
Graph Theory
(a) Prove that the distance function $d(u, v)$ on a pair of vertices of a graph satisfies the triangle inequality: $$d(u, v) + d(v, w) \geq d(u, w).$$
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5풀이1. The distance $d(u, v)$ between two vertices $u$ and $v$ is the length of the shortest path connecting $u$ and $v$. 2. Suppose $d(u, v) + d(v, w) By definition,$d(u, v)$is the length of the shortest path from$u$to$v$, and$d(v, w)$is the length of the shortest path from$v$to$w$. However,$d(u, w)$ is the length of the s..
→2024.12.28
Graph Theory
Let $T$ and $T'$ be two spanning trees of a connected graph $G$. For $e \in E(T) - E(T')$, prove that there is an edge $e' \in E(T') - E(T)$ such that $T' + e - e'$ and $T - e + e'$ are both spanning trees of $G$.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5Solution1. Consider an edge $e \in E(T) - E(T')$. Since $e$ is not in $T'$, adding $e$ to $T'$ results in the graph $T' + e$.Because $T'$ is a spanning tree, it already spans all vertices of $G$.This means there is a path in $T'$ between any two vertices. Adding $e$, which is incident to two vertices already connected by a path in $T'..
→2024.12.28
Graph Theory
Let F be a maximal forest of G. Show that: $e(F) = n(G) − c(G)$, where e, n, and c are the number of edges, vertices, and compo-nents, respectively.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5Solution1. $G$ has $c(G)$ components. Each component $H$ of $G$ is connected and contains a spanning tree $F \cap H$, as shown in part (a).2. A spanning tree with $k$ vertices has exactly $k-1$ edges, since a tree with $k$ vertices has $k-1$ edges by definition.3. Therefore, for each component $H$, if $H$ has $n(H)$ vertices, the span..
→2024.12.28
Graph Theory
Let F be a maximal forest of G. Show that: (a) For every component H of G, F ∩ H is a spanning tree of H
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5 Solution1. A component $H$ of $G$ is a connected subgraph of $G$. Thus, $H$ is connected by definition. $F$ is a maximal forest of $G$, meaning that $F$ is an acyclic subgraph of $G$ and spans all components of $G$. 2. Since $F$ is a forest, it contains no cycles. Thus, $F \cap H$, as a subgraph of $F$, must also be acyclic. 3. $F..
→2024.12.28
Graph Theory
What is the minumum number of cycles in graphs with n vertices and m edges?
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5Solution1. Suppose that there is a graph with $n$ vertices and no edges. 2. As we add edges to the graph, we need to determine whether each new edge creates a cycle. A cycle is formed when there is already a path between the two vertices before the edge is added. 3. At the beginning, there are $n$ disconnected vertices. By adding $n..
→2024.12.28
Graph Theory
Let T be a nontrivial tree. Determine the minimum possible number of maximal indepen-dent sets in T . Determine all the possible structure of T achieving the minimum number.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5 Solution1. In a tree, there are leaf vertices and non-leaf vertices. If we take a maximal independent set that includes a leaf vertex, we can also construct a different maximal independent set that excludes that leaf and includes its neighbor instead. 2. Thus, there are always at least two distinct maximal independent sets in any t..
→2024.12.28

• 이전
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• ···
• 27
• 다음