離散數學›Ch6 圖論
第 10 題/共 34 題
◀ LS 10/34
10. 正則圖、超立方體圖、平面圖、完全二部圖
#LS-06-010易正則圖超立方體圖平面圖完全二部圖
  1. Please answer TRUE or FALSE for the following statements and give CONCISE explanations.

(a) (2 points) A simple graph is called regular if every vertex of this graph has the same degree. An nn-cube, denoted by QnQ_n, is a graph that has vertices representing the 2n2^n bit strings of length nn. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position. QnQ_n is regular.

(b) (2 points) Let VnV_n and EnE_n respectively be the number of vertices and edges of QnQ_n, the nn-cube. Then, E1=1E_1 = 1, E2=4E_2 = 4, and En+1=2Vn+EnE_{n+1} = 2V_n + E_n.

(c) (2 points) The complete bipartite graphs K2,3K_{2,3} and K3,3K_{3,3} are planar.

📄 交大110
跳轉到第題
▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論
本章題號 · 1–20 / 34