전체 글
Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G).
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 10Solution1. ($\Rightarrow$) If $G$ is $m$-colorable: Assume there exists a proper $m$-coloring $f : V(G) \to {1, 2, \ldots, m}$. For each color $i$, let $I_i = {v \in V(G) \mid f(v) = i}$. Each $I_i$ is an independent set in $G$. Consider the Cartesian product $G \square K_m$. The vertex set of $G \square K_m$ is:$$V(G \square K_m) ..
The Turan graph $T_{n,r}$ is the compelete $r$-partite graph with $b$ partite sets of size $a+1$ and $r - b$ partite sets of size $a$, where $a = \lfloor n/r \rfloor$ and $b = n - ra$.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7Solution1. Prove that $e(T_{n,r}) = (1 - \frac{1}{r})\frac{n^2}{2} - \frac{b(r-b)}{2r}$.a. The degree of a vertex $v$ in an independent set of size $a$ is $\deg_G(v) = n - a$.- The degree of a vertex $v$ in an independent set of size $a+1$ is $\deg_G(v) = n - a - 1$.b. For independent sets of size $a$, there are $r-b$ such sets, each ..
Find ordering of the vertices of G for which the greedy algorithm requires 3, and 4 colors,respectively.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9Solution1. Let the index of colors be $\bigcirc 2. Let the ordering of vertices of $G$ be $g, d, e, c, f, a, b, h$.In this order, Greedy Coloring requires 3 colors. (See the left graph below.)3. Let the ordering of vertices of $G$ be $g, e, d, f, b, h, c, a$.In this order, Greedy Coloring requires 4 colors. (See the right graph below...
Let $e_i(G)$ denote the number of vertices of G whose degree is strictly greater than i. Use the greedy algorithm to show that if $e_i(G) \leq i + 1$ for some i, then $\chi(G) \leq i + 1$. Find an example H that satisfies $e_4(H) \leq 5$ and compute χ(H)
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9Solution1. Decide the order of all vertices.2. First, place all the vertices with $deg_G(v) > i$. Next, place the remaining vertices.3. By the given definition of $e_i(G)$, the number of vertices with $deg_G(v) > i$ is $e_i(G)$.By the given assumption, $e_i(G) \leq i+1$.Thus, $e_i(G)$ is at most $i+1$.4. Apply the Greedy Coloring algo..
For every graph G, show that there is an ordering of the vertices of G such that the numberof required colors from Greedy Algorithm is exactly χ(G). (You should describe how togive such an order.)
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 9Solution1. Assume that the graph $G$ can be properly colored with exactly $\chi(G)$ colors. Remember that each color class forms an independent set. 2. Using this proper coloring, define the vertex order as follows: a. List all vertices in the color class corresponding to color 1. b. Next, list all vertices in the color class co..
Choose two graphs and determine the chromatic numbers of them. Give your explanationfor each case.
Solution1. Figure (a)The graph in Figure (a) includes the subgraph $C_5$ (observe the outer 5 vertices).If the graph is 2-colorable, it must have an even number of vertices. However, $C_5$ has an odd number of vertices (5).Thus, $ \chi(C_5) \geq 3 $.Below is Figure (a):I marked the graph with 3 proper colors (1, 2, 3). It is 3-colorable.Therefore, $ \chi(\text{graph (a)}) = 3 $.2. Figure (b)The ..
Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8Solution1. Since $G$ is a 3-regular graph, $\delta(G) = 3$. Thus, $\kappa(G) \leq \kappa'(G) \leq \delta(G) = 3$.2. Consider $\kappa(G) = 0$:If $G$ is disconnected, $\kappa'(G) = 0$.Thus, $\kappa(G) = \kappa'(G) = 0$.3. Consider $\kappa(G) = 1$:Let the vertex cut $S = {v_1}$.There are two components $C_1$ and $C_2$ in $G \setminus S$...
Use Menger’s Theorem ($\kappa$(x, y) = $\lambda$(x, y) when $xy$ $\notin$ $E(G)$) to prove that $\alpha'(G) = \beta(G)$ when $G$ is bipartite.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8Solution1. Suppose $G$ is a bipartite graph. We can divide $G$ into two independent and disjoint vertex sets $X$ and $Y$. 2. For $x \in X$ and $y \in Y$, add an edge ${x, y}$ to $G$ and let this new graph be $G'$. 3. In $G'$, consider: $\lambda_{G'}(x, y)$: the maximum number of internally disjoint $x, y$-paths, and $\kappa_{G'}(x..
Let G be a simple graph of even order n having a set S of size k such that o(G-S) > k. Prove that G has at most $\binom{k}{2} + k(n-k) + \binom{n-2k-1}{2}$ edges, and that this bound is best possible. Use this to determine the maximum size of a simple $n$
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7Solution1. The total number of edges in $G$ can be expressed as: $$ |E(G)| = e(G[S]) + |[S, \bar{S}]| + e(G[\bar{S}]), $$ where $e(G[S])$ is the number of edges within $S$, $|[S, \bar{S}]|$ is the number of edges between $S$ and $\bar{S}$, and $e(G[\bar{S}])$ is the number of edges within $\bar{S}$. 2. Since the size of $S$ i..
Prove or disprove: If G is a 3-regular graph with at most two cut-edges, then G has a 1-factor.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8ProblemProve or disprove: If $G$ is a 3-regular graph with at most two cut-edges, then ( G ) has a 1-factor.Solution1. We will use Tutte's theorem and Proposition 4.1.12: If $S$ is a set of vertices in a graph $G$, then: $$ |[S, \bar{S}]| = \sum\limits_{v \in S} d(v) - 2e(G[S]), $$ where $|[S, \bar{S}]|$ represents the numbe..
Prove or disprove: (a) every graph with connectivity 4 is 2-connected. (b) every k-connected graph is k-edge-connected.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 8Solution(a) Every graph with connectivity 4 is 2-connected.For Connectivity 4 graph, we need to delete at least 4 vertex to disconnect the graph. And for 2-connected graph, If we delete one vertex it still remain connected. By the definition of connectivity and $k$-connected, It is true.(b) Every k-connected graph is k-edge-connected...
AWS 서버비용절감 계획 및 기록 (3) - AWS CLI 사용하기
AWS CLI가 필요해져서 설정 방법을 기록해두려한다. 1. 설치curl "https://awscli.amazonaws.com/AWSCLIV2.pkg" -o "AWSCLIV2.pkg"sudo installer -pkg AWSCLIV2.pkg -target /aws --version # 설치확인 2. AWS CLI 인증설정aws configure인증정보구성을 위한 명령이며, 4가지가 요구된다.Access Key ID: AWS 계정의 Access Key ID.Secret Access Key: AWS 계정의 Secret Key.Default region: AWS 리전 (나는 서울리전에 해당하는 ap-northeast-2을 이용했다)Default output format: 기본적으로 json 사용. 3. Acc..