이것저것 공부방

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
웹 프로그래밍/배포
AWS 서버비용절감 계획 및 기록 (1) - 구현계획
1. 현재 상황 40달러 안밖의 비용이 발생하고 있음. 이중 거의 절반을 차지하는 부분이 Amazon Elastic Compute Cloud - Compute 영역으로 보인다. 이 부분을 줄여보고자한다. 현재 나는 서버를 항상 켜두고 있기 때문에 인스턴스 사용시간이 비용을 증가시키는 가장 유효한 변수일 것으로 생각된다.  2. EC2 인스턴스를 사용자 요청에 따라 껐다 켜는 구조로 변경해본다.- SEO를 본격적으로 하지 않았기에, 유입이 크지 않은 상태이다. 사용자가 들어올때만 서버를 켜도 충분할 것이다.필요할 것 같은 몇가지 키워드를 찾아 공부해보고, 가능성을 조사해본다.* AWS Lightsail, Lambda 기반 서버리스 구조, CloudWatch Alarm 3. 구현흐름ChatGPT는 다음과 같..
→2025.01.07
Graph Theory
Prove that $κ(G) = δ(G)$ if G is simple and $δ(G) ≥ n(G)−2$. Prove that this is best possible for each n ≥ 4 by constructing a simple n-vertex graph with minimum degree n − 3 and connectivity less than n − 3.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7아래를 참고해서 작성한 풀이인데, 풀이가 조금 찝찝하다. 조교는 한두장 분량의 원래 매우 긴 풀이를 기대했다고 한다. 다른 괜찮은 풀이를 생각해보는게 좋겠다.https://seongqjini.com/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-graph-theory-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-prove-that-%CE%BAg-%CE%B4g-if-g-is-simple-and-%CE%B4g-%E2%89%A5-ng-%E2%88%92-2-prove-that/Solution1. Since $ \delta(G) \geq n(G) ..
→2024.12.29
Graph Theory
For each n ∈ N, find an n-vertex graph such that $κ′(G) > κ(G)$.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7Solution1. If the graph is initially disconnected,  $\kappa'(G) = 0$ . Thus, $\kappa(G) = \kappa'(G) = 0$. Therefore, we will only consider connected graphs.2. For , n = 1 :$\kappa(G) = \kappa'(G) = 0$ is trivial.3. For , n = 2 :The path graph ,$P_2$  is the only connected graph, and  $\kappa(G) = \kappa'(G) = 1$ is trivial.4. For ,..
→2024.12.29
Graph Theory
Draw the Cartisian product G□H, where G = K2,3 and H = K3.
문제출처광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7SolutionLet ( G ) be a bipartite graph, where the vertex sets are divided into two independent sets: $$U = \{00, 01\}, \quad V = \{10, 11, 12\}.$$ Let ( H ) be a graph with vertex set: $$V(H) = \{20, 21, 22\}.$$  The vertex set of ( G \square H ) is the Cartesian product of the vertex sets of ( G ) and ( H ):$$V(G \square H) = {(u,..
→2024.12.29

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