2020-04-10 Fundamental Concept III

video

tags: 圖論

講義: fundamental_concept_1_2020

p.23 Recall biconditional method

Direct method

$P\Rightarrow Q$
Contrapositive metjod

$\sim Q\Rightarrow \sim P$
Contradiction

$\sim (P\wedge \sim Q)$

三個等價敘述

P.24

• Theorem :
  An edge is a cut-edge if and only if it belongs to no cycle.

• 補充 cut-edge : an edge whose deletion increases the number of components.
  

proof:
e=(x, y): an edge
H-e is connected iff e belongs to a cycle

1. $!P\Rightarrow !Q$
   H-e is connected 就代表 e 不是cut-edge(!P)

P.25

2. $!Q\Rightarrow !P$
   e 在 cycle裡(!Q)

P.26

• Lemma: Every closed odd walk contains an odd cycle.

odd walk指的是 edge 是odd
close就是出發點和終點一樣(走回出發點)

Case 2 : 拆成兩半，一邊odd，一邊even

basis到induction的過程要補上假設:長度大於1，小於W的close odd walk，contain 一個 odd cycle (

$StrongInduction$)

P.27

Note:

• disjoint (set和set之間): set之間沒有共同元素
• independent(set裡的element):同一個set中的點沒有連線

P.28 & Extra

ref1

• Theorem:

A graph is bipartite if and only if it has no odd cycle.

$Proof:$

$\Rightarrow :$
堆和堆之間連線如果要形成cycle，就必須出去再回來，這樣形成的只會是even cycle，就算是沒有cycle也不會是odd cycle

$\Leftarrow :$

• Case 1: G裡沒有cycle

  • 把每一個edge的兩端放在不同堆裡

• Case 2: G裡不是odd cycle

  • 分兩堆最常用的技巧是長度(odd、even)

真的猛
Omnom

P.29 Eulerian

• Def : closed trail containing all edges.

  • Trail is a walk with no repeated edge
  • $circuit$ : closed trail

P.30

• Lemma :
  If every vertex v of a graph G has degree at least 2, then G contains a cycle.

1. u 如果是 endpoint of maximal path
   $P$，那麼
   $u$ 的 neighbor 都會在
   $P$ 上。

考慮在u左端新增一個新的vertex x的話，那麼u就不會是endpoint

2. $u$ 的degree至少為2
   $\to$
   $u$ 的neighbor
   $v_1$,
   $v_2$也在
   $P$上
   
   $v_1$,
   $v_2$中間至少有2種path：¹在
   $P$上、²透過
   $u$

P.31

• Theorem:
  A graph G is Eulerian if and only if it has at most one nontrivial component and its vertices all have even degree.

Note:
trival component: no edges
(但是1個點的Graph是Eulerian)

• $proof$

$\Rightarrow$
(1).如果有2個nontrivial component，根本不可能是尤拉圖，因為沒有trail可以連他們兩個
(2).點必須要一進一出，所以degree必須是偶數

$\Leftarrow$
Prove by Strong Induction on the number of edges m.

Basis: m=0 一個點
(Not violate def. of Eulerian graph)

Induction: m>0. (In fact, by assumption, m should ≥ 2.)
The nontrivial component has a cycle

$C$.
(Recall Lemma: If every vertex

$v$ of a graph

$G$ has degree at least 2, then

$G$ contains a cycle.)

Let

$G^{\prime }=G-E(C)$
將

$G$的cycle

$C$扣除(每個vertices degree少2)，產生諸多component

By induction hypothesis, each component of G’ has an Eulerian circuit.
Merge these circuits to obtain an Eulerian circuit of G.
(增加2 edges，一進一出)

P.33

• Theorem:
  For a connected nontrivial graph with exactly 2k odd vertices, the minimum number of trails that decompose it is max{k, 1}.

Recall: trail:no repeated edge
G=(V,E)是connected. 有2k個degree為odd的點

$\Rightarrow$ decompose之後，最少trail數為max{k,1}

P.35 Vertex Degree and Counting

Maximum degree:

$\mathrm{\Delta }(G)=ma{x}_{v\in V(G)}\{d_G(v)\}$
Minimum degree:

$\delta (G)=mi{n}_{v\in V(G)}\{d_G(v)\}$

Def: regular graph

$\mathrm{\Delta }(G)$ =

$\delta (G)$

$k$-regular: common degree is

$k$

P.36 Vertex Degree and Counting (Conti.)

$Def$:
order of a graph : number of vertices or |V(G)|
size of a graph :　number of edges or |E(G)|

$Proposition:(Degree-SumFormula)$

$\sum _{v\in V(G)}d(v)=2e(G)$,

$\mathrm{\forall }$ graph

$G$

$Corollary$ 2: 奇數degree的點有偶數個，由proposition可以得知不可能有偶數個(

$2e(G)$ is even)

P.37 Vertex Degree and Counting (Conti.)

Proposition:
If

$k>0$, then a

$k$-regular bipartite graph has the same number of vertices in each partite set.

$proof$:
拆成X和Y兩邊，edge分佈於X,Y之間，然後由於是k regular，X堆和Y堆分到的點的個數會一樣

P.38

Proposition:
The minimum number of edges in a connected graph with

$n$ vertices is

$n-1$. (其實就是tree)

$proof$:
用到n vertices 和 k edges 至少有 n-k component，如果k=n-2，那就會有2個components，那就不會是connected graph

P.39

P.40

Proposition:

If

$G$ is a simple

$n$-vertex graph with

$\delta (G)\ge \frac{(n-1)}{2}$, then

$G$ is connected.
(

$\delta (G)$是G裡最小的degree)

$proof$:

$G$ is simple

$\Rightarrow$

$|N(u)|\ge \delta (G)\ge \frac{n-1}{2}$ , similarly for

$v$
(simple: 一個neighbor 對應一個degree)
N (u)是指neighbor數量 = u 點 degree

對於

$u\ne v$, 且

$u,v$不相連,

$|N(u)\cup N(v)|\le n-2$ (指的是u和v的common neighbor數會小於等於n-2，u,也就是扣掉u、v這兩點)

(

$u,v$相連的話會出錯：e.g.

$|N(u)\cup N(v)|=n$)

$|N(u)\cap N(v)|=|N(u)|+|N(v)|-|N(u)\cup N(v)|$

$\ge \frac{n-1}{2}+\frac{n-1}{2}-(n-2)=1$
(

$u,v$至少有一個共同neighbor

$\Rightarrow$

$u,v$ are connected )
(意思是說即使任兩個不相鄰的點都還是可以透過一個common neighbor來走道另一邊，前提是一開始的假設要先成立)

P.41

Theorem: Every loopless graph

$G$ has a bipartite subgraph with at least

$\frac{e(G)}{2}$edges.

關於第3點的說明：
因為H是edge數最多的bipartite graph，所以改變v neighbor的選法時，不應該增加H的edge

$i.e.$ 將

$d_H(v)$拆成兩部分時，當然選最大的啊(murmur)