분류 전체보기

Graph Theory
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..
→2025.01.14
Graph Theory
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..
→2025.01.14
Graph Theory
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 ..
→2025.01.14
Graph Theory
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$...
→2025.01.14
Graph Theory
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..
→2025.01.14
Graph Theory
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..
→2025.01.14
Graph Theory
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..
→2025.01.14
Graph Theory
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...
→2025.01.14
웹 프로그래밍/배포
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..
→2025.01.08
웹 프로그래밍/배포
AWS 서버비용절감 계획 및 기록 (2) - AWS S3, CloudFront
1. 구조 변화계속 EC2를 사용해왔기에 Lamda의 구조가 잘 그려지지 않는다. 원래의 구조와 비교하여 생각해보려한다. 1) 기존구조: React + DRF + Docker Swarm on EC2React: 앱을 정적파일로 빌드하고 Nginx 컨테이너로 제공함.DRF로 API 제공. /api 엔드포인트로 통일시켜둬서 이걸로 구분하고 Nginx를 이용해 서빙함.Docker Swarm: EC2에서 컨테이너 오케스트레이션 및 확장성을 관리함. 2) Lambda로 전환 이후: Lambda는 서버리스 기반이다.React는 정적파일로 빌드하고 S3와 CloudFront를 사용해서 배포한다. CloudFront는 CDN으로 사용자에게 빠르게 전달.DRF를 Lambda 함수로 분리해서 서버리스로 전환 2. Front..
→2025.01.08

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