그래프이론 (Graph Theory) 문제를 풀려고 합니다. 이번에 풀려고 하는 문제는 “What is the minumum number of cycles in graphs with n vertices and m edges?” 입니다. vertex 가 n개 있고 edge가 m개 있는 graph 가 갖고 있는 최소의 cycle 갯수를 의미합니다.
그래프이론 (Graph Theory) 문제 풀이
풀려고 하는 문제를 다시 recap 해보겠습니다.
What is the minumum number of cycles in graphs with n vertices and m edges?
풀이)
m 이 n-1 보다 작거나 같은 경우엔 graph 에 cycle이 있다고 보장하지 못한다.
그러므로 m이 n보다 크거나 같다고 가정을 하자.
n 개의 vertex가 있고 거기에 m개의 edge를 한개 씩 만들어서 vertex가 n개이고 edge수가 m개인 graph를 만들 예정이다. 어느 상황에서든 edge를 놓는다면 아래의 두 경우중에 한가지 경우가 발생한다.
- 서로다른 component에 있는 서로 다른 두개의 vertex를 이어버려서 component의 총 갯수를 줄이는 경우. 이 경우에는 cycle이 생기지 않는다.
- 하나의 component내에 있는 두 vertex를 잇는 edge를 만드는 경우. component 안에 있는 두 vertex는 path 로 연결되어있다. 따라서 component 내의 두 vertex를 잇는 새로운 edge를 만든다는 것은 cycle을 추가적으로 만든다는 것이다.
그런데, 처음에 vertex의 갯수는 n개라는 것에 주목을 하자. edge를 아무리 서로 다른 두 component의 두 vertex를 잇도록 만들다 한들, component 의 갯수를 줄이게 하는 edge의 수는 최대 n-1개 이다. 그러면 남은 m-(n-1) 개의 edge의 동일한 component 내에 있는 두 vertex를 잇게 해서 cycle을 추가한다. 그러므로 cycle의 최소 갯수는 m-n+1 개이다.
참고할만한 글:
- [그래프이론(Graph Theory)] Deleting a vertex of degree ∆(G) cannot increase the average degree.
- [그래프이론(Graph Theory) 문제풀이] Prove or disprove: K9 decomposes into copies of C9.
- [그래프이론(Graph Theory)] Use induction to prove that if a graph does not have an odd cycle then it is bipartite.
- [그래프이론(Grpah Theory)] Prove that the Petersen graph has no cycle of length 7.
- [그래프이론(Graph Theory) 문제풀이] Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
- [그래프이론(Graph Theory) 문제풀이]Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
- [그래프이론 문제풀이] Let u and v be adjacent vertices in a simple graph G. Prove that uv belongs to at least d(u) + d(v) − n(G) triangles in G.
- [그래프 이론(Graph Theory)-1] k-set과 k-subset
- [그래프이론(Graph Theory) 문제풀이] Deleting a vertex of degree δ(G) cannot reduce the average degree.
- [그래프이론(Graph Theory) 문제풀이] Prove or disprove: Every tree T has at least ∆(T) leaves.
- [그래프이론 (Graph Theory) 문제풀이] Prove that the number of simple Eulerian graphs with vertex set {1, 2, · · · , n} is 2 ( n−1 2 ).
- [그래프이론 (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 ∈ V (G). Hence, conclude that G is regular.
- [그래프이론(Graph Theory) 문제풀이] Use induction on n(G) to prove that every nontrivial loopless graph G has a bipartite subgraph H such that H has more than e(G)/2 edges.
- [그래프이론 (Graph Theory) 문제풀이] Let T be an n-vertex tree having one vertex of each degree i with 2≤i≤k; the remaining n-k+1 vertices are leaves. Determine n in terms of k.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 4 문제