분류 전체보기

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
Graph Theory
Let $G$ be a triangle-free simple $n$-vertex graph such that every pair of non-adjacent vertices has exactly two common neighbors. Prove that $n(G) = 1 + \binom{d(x)+1}{2}$, where $x \in V(G)$. Hence, conclude that $G$ is regular.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4 Solution1. Choose any vertex $x$ in $G$. $x$ has $d(x)$ neighbors, and let them be $v_1, v_2, \dots, v_{d(x)}$, where $d(x)$ is the degree of $x$. 2. Since $G$ does not have triangles, there are no edges between $v_1, v_2, \dots, v_{d(x)}$. 3. The number of vertices non-adjacent to $x$ is $n - d(x) - 1$. This is calculated as: (T..
→2024.12.28
Graph Theory
Prove that the number of simple Eulerian graphs with vertex set $\{1, 2, \dots, n\}$ is $2^{\binom{n-1}{2}}$.
Solution1. I will define two sets of graphs:$G_{n-1}$: The set of simple graphs with vertex set ${1,2,\dots,n-1}$.$E_n$: The set of Eulerian graphs with vertex set ${1,2,\dots,n}$.2. I will show that the sizes of these two sets are the same by establishing a bijection between $G_{n-1}$ and $E_n$.3. Check Injectivity:i. Given $G \in G_{n-1}$, construct a graph $E \in E_n$ by adding the $n$-th ver..
→2024.12.28
Graph Theory
Prove or disprove: Every tree T has at least $∆(T)$ leaves.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4Solution1. Let $v$ be a vertex in $T$ with degree $\Delta(T)$, where $d(v) = \Delta(T)$. That is, $d(v)$ is the degree of vertex $v$.2. $v$ has adjacent vertices $w_1, w_2, \dots, w_{d(v)}$. That is, there exist edges $vw_i$ incident to $v$ for $1 \leq i \leq d(v)$.3. Now, for every edge $vw_i$ incident to $v$, take a longest path st..
→2024.12.28
Graph Theory
Prove or disprove: If G is an n-vertex simple graph with maximum degree ⌈n/2⌉ andminimum degree ⌊n/2⌋ − 1, then G is connected.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4 Solution1. Let $C_u$ be a connected component of $G$ that contains the vertex $u$ with the maximum degree, and $C_v$ be a connected component of $G$ that contains the vertex $v$ with the minimum degree.2. I will identify the contradiction that arises when $C_u$ and $C_v$ are disjoint.3. $d(u)$ is $\lceil n/2 \rceil$, where $d(u)$ is..
→2024.12.28
Graph Theory
Let T be a tree with average degree d. In terms of d, determine $n(T)$.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4 Solution1. Since a tree is a connected graph with no cycles, $|E_T| = n(T) - 1$, where $|E_T|$ is the number of edges in $T$. 2. The average degree $d$ is: $$d = \frac{\sum\limits_{v \in V(T)} d(v)}{n(T)},$$ where $d(v)$ is the degree of vertex $v$, and $V(T)$ is the vertex set of $T$. 3. In a graph, the sum of the degre..
→2024.12.28
Graph Theory
Prove or disprove: Every graph with fewer edges than vertices has a component that is a tree.
문제출처광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 4Solution1. Let's consider a graph $G$ such that $|E_G| 2. Suppose that$G$has connected components$G_1, G_2, \dots, G_k$. Each$G_i$is a connected subgraph. If$G_i$is not a tree, then$G_i$must have a cycle.3. A key property of a tree is that$|E| = |V| - 1$. To add a cycle to a tree, we need at least one additional edge. Thus..
→2024.12.28
Graph Theory
Which of the following are graphic sequences? Provide a construction.
가장 큰 차수의 정점에서 정점을 하나 제거하고, 차수를 줄여가는 식으로 그래프를 단순화하고 다시 복구해가는식으로 확인할 수 있음.e.g. 5,5,5,3,2,2,1,1-> (5x), 4,4,2,1,1,1,1-> (5x), (4x), 3,1,0,0,1,1 -> (sort) 3,1,1,1,0,0 -> 이 정도했으면 그려짐. 여기서부터 정점을 하나씩 채워서 복구하면됨. 1. 5,5,4,3,2,2,2,1 2. 5,5,5,3,2,2,1,1 3. 5,5,4,4,2,2,1,1
→2024.12.28

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