이것저것 공부방

Graph Theory
For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6Solution아래 풀이는 일반화된 풀이라기엔 부족한 감이 있다. 필자는 연결그래프만을 상상했기에 이런 풀이를 작성했으나, n=16, n=18 케이스에 K4를 추가해가는식으로 그래프를 구성하면 일반화된 풀이를 구성할 수 있다. The above figure shows a 3-regular graph (( n = 16 )) having no 1-factor, as demonstrated in Problem 5 using Tutte's theorem.Using the same definitions of ( v^* ) and ( G_i ) from Problem 5, let the subgraphs ..
→2024.12.28
Graph Theory
For each k > 1, construct a k-regular simple graph having no 1-factor.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6Solution아래 풀이엔 논리적 오류는 없으나, 아래에 그려둔 k=3, k=5 예시에 K4를 추가하는 방식으로 그래프를 구성해보면 더 쉽게 표현할 수 있다. 규칙성을 찾아보고 예시의 두 그래프를 각각 G1, G2로 정의하고, Union 기호를 이용해 K4를 몇개 추가하면 조건을 완성시킬 수 있을지 검토해보면된다.   We will consider two cases:Case 1: $k$ is evenImagine the complete graph $K_{k+1}$.This is a $k$-regular graph with $k+1$ vertices.Since $K_{k+1}$ has an odd..
→2024.12.28
Graph Theory
Exhibit a maximum matching in the graph below, and use various results that we learned so far to give a short proof that it is a maximum matching.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 6SolutionFor the given matching $M$, $|M| = 8$.In $M$, there is no augmenting path.We will prove that if a matching $M$ has no augmenting path, then $M$ is a maximum matching.Proof:1. Define a matching $M$ with no augmenting path.2. Assume, for contradiction, that $M$ is not a maximum matching.That is, there exists a larger matching $M..
→2024.12.28
Graph Theory
Recover the corresponding tree with Pr¨ufer code (1, 3, 5, 7, 6, 1, 6, 4).
Length of prufer code is 8. Thus tree have 10 vertices. I defined set of degree of each vertices D. Every vertex initially has a degree of 1, and the degree of each vertex thatappears in the prufer code increases by the number of times it appears. Thus, the degreeset can be defined as D = (3, 1, 2, 2, 2, 3, 2, 1, 1, 1). From the prufer code and D, tree canbe constructed through the following pro..
→2024.12.28
Graph Theory
Assign integer weights to the edges of Kn. Prove that the total weight on every cycle iseven iff the total weight on every triangle is even.
Solution1. Sufficient Condition: A triangle is a 3-cycle. Thus, if the total weight of every cycle is even, then the total weight of every triangle is also even. 2. Necessary Condition: We will use mathematical induction to prove this. Steps*: Base Case: For cycles of length 3 (i.e., triangles), we know by assumption that the total weight of every triangle is even. Inductive Hypothesis: ..
→2024.12.28
Graph Theory
Determine which trees have Pr¨ufer codes that (a) contain only one value, (b) containexactly two values, or (c) have distinct values in all positions.
Solution1. Prufer code contains only one value Let the Prufer code $P = [k, k, \dots, k]$. Steps*: Number of vertices: The Prufer code has a length of $n-2$, so the tree has $n$ vertices. These vertices are ${1, 2, \dots, n}$. Decoding the Prufer code: In each step of the decoding process, the smallest leaf is selected and is made adjacent to the vertex corresponding to the first value in ..
→2024.12.28
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

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