離散 part6 - HackMD

--- title: 離散 part6 --- {%hackmd @NTNUCSIE112/DM_card %} # Graph Ch.6.2 The Pigeonhole Principle Ch.10 Graphs Reading assignment: 6.2, 10.2-10.5 ## Ch.06 ### 6.2 ## Ch.10 ### 10.2 Graph Terminology and Special Types of Graphs #### Hall's Marriage Theorem > The bipartite graph $G = (V,E)$ with bipartition $(V-1,V_2)$ has a complete matching from $V_1$ to $V_2$ if and only of $|N(A) \geq |A|$ for all subsets $A$ of $V_1$ (Necessity "the only if part"): the vertices matched with must lie in , and these vertices are distinct. (Sufficiency "the if part"): We prove by induction on the size of |$V_1$|, then we size of . - Induction basis: if , then we may match the vertex in with any of its neighbor(s). - Inductive step: assume that theorem holds for , for some integer at least . We claim that the theorem holds for . -- Case (i): all subset of size at most satisfy . -- Case (ii): there exists a subset of size at most such that |V1 | |V1 | = 1 V1 |V1 | ≤ k k 1 |V1 | = k + 1 A ⊆ V1 k |A| < |N(A)| A ⊆ V1 k |A| = |N(A)|  - Case (i): Remove an edge $e$, along with its endpoints $u$ and $v$, and let the resulting bipartite graph be $G'$ with bipartition $(V_1'',V_2'')$. - For $A \subseteq V_1, |A| < |N(A)| \leq |N(A)|$  - Case (ii): (there exists a subset $A\subseteq V_1$ of size at most $k$ such that |A| = |N(A)|.) - Consider the bipartite graph induced by $A \cup N(A)$. Since $|A| < k$, by the inductive hypothesis there is a complete matching $M_1$ from $A$ to $N(A)$. - Consider the bipartite graph with $(V_1-A, V_2-N(A))$. ### 10.3 Representing Graphs and Graph Isomorphism #### 10.3.5 Isomorphism of Graphs 同構 - Two simple grapsh $G_1$ and $G_2$ are isomorphic if there exists a bijection - $f:V_1\to V_2$ with property that for $a,b \in V_1$, $a$ and $b$ are adjacent in $G_1$ $f(a)$ and $f(b)$ are adjacent in $G_2$ - Function $f$ is called an isomorphism #### 10.3.6 Determining whether Two Simple Graphs are Isomorphic - NP problem ### 10.5 Euler and Hamilton Paths #### 10.5.1 Introduction #### 10.5.2 Euler Paths and Circuits #### 10.5.3 Hamilton Paths and Circuit  ### Exercise - self-complementary graphs - For a simple graph $G$, its complement, denoted by $\overline{G}$, is a simple graph satisfying $\{u,v\} \in E(G) \iff \{u,v\} \notin E(\overline{G})$ #### Ramsey Theorem Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Then, either there are three mutual friends or there are mutual enemies. (In other words) Let $G$ be a graph with six vertices. Then either $G$ or $\overline{G}$ has $K_3$ as a subgraph.