Seongq

그래프이론 (Graph Theory) 문제 풀이 해보겠습니다. 이번 글에서 풀이할 문제는 “Let T be a nontrivial tree. Determine the minimum possible number of maximal independent sets in T. Determine all the possible structure of T achieving the minumum number.” 입니다. 그래프이론 (Graph Theory) 문제풀이 다시 문제를 보겠습니다. Let T be a nontrivial tree. Determine the minimum … Read more

그래프이론 (Graph Theory) 문제풀이 하겠습니다. 이번에 풀 문제는 “Let W be a closed walk in a graph G. Let H be the subgraph of G consisting of edges used an odd number of times in W. Prove or disprove: The degree of v in H, deg_H(v), is even for every v ∈ V (G).” 입니다. … Read more

그래프이론 (Graph Theory) 문제풀이를 해보겠다. 이번에 풀 문제는 “Present the proof we learned in class using 2-switch method to show that there is a simple graph with degree sequence d’ = 432222111 from the following simple graph G with degree sequence d = 6543333111. Start with G − v.” 이다. 그래프이론 (Graph Theory) 문제풀이 이번에 … Read more

그래프이론 (Graph Theory) 문제를 풀려고 합니다. 이번에 풀려고 하는 문제는 “What is the minimum number of edges of an n-vertex graph with diam(G) = 2 and ∆(G) = n−2?” 입니다.  maximum degree 가 n-2 이고 diameter 가 2 인 graph 는 몇개의 edge를 갖냐고 물어보는 문제입니다. 그래프이론 (Graph Theory) 문제 풀이 풀려고 하는 문제를 다시 … Read more

그래프이론 (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 … Read more

그래프이론 문제를 풀려고 한다. 풀려는 문제는 “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.” 이다. n개의 vertex로 구성된 Tree가 있다고 하자. i=2,3,…,k 마다 i를 degree를 갖는 vertex가 한개씩 존재하고 나머지 vertex는 다 leaf라고 한다. 이 때 … Read more