// 汉密尔顿图充分条件证明

# Graph

## Introduction to Graphs

**Definition:**

- A
`simple graph`

$G=(V,E)$ consists of $V$, a nonempty set of vertices, and $E$, a set of unordered pair of distinct elements of $V$ called edges. - A
`multigraph`

$G=(V,E)$ consists of a set $V$ of vertices, and a set $E$ of edges,and a function from $E$ to $\left\{\left\{u,v\right\}|u,v\in V,a\neq v\right\}$. The edge $e_1$ and $e_2$ are called multiple or parallel edges if $f(e_1)=f(e_2)$. - A
`pseudograph`

$G=(V,E)$ consists of a set $V$ of vertices and a set $E$ of edges, and a function from $E$ to $\left\{\left\{u,v\right\}|u,v\in V\right\}$. An edge is a loop if $f(e)=\left\{u,u\right\}=\left\{u\right\}$ for some $u\in V$.

**Remark:**

To summarize,

`Pseudograph`

are the most general type of undirected graphs since they contain loops and mutiple edges.`Multigraphs`

are undirected graphs that may contain multiple edges but not have loops.`Simple graph`

are undirected graphs with no multiple edges or loops.

**Definition:**

- A
`directed graph`

$G=(V,E)$ consists of a set of vertices $V$, and a set of edges $E$ that are ordered pairs of elements of V. - A
`directed multigraph`

$G=(V,E)$ consists of a set of $V$ of vertices and a set $E$ of edges, and a function from $E$ to $\left\{\left\{u,v\right\}|u,v\in V,a\neq v\right\}$. The edges $e_1$ and $e_2$ are called parallel edges if $f(e_1)=f(e_2)$.

```
Table 1 GRAPH THERMINOLOGY
//----------------------------------------------------------------------------
Type Edges Multiple Edges Allowed? Loop Allowed?
Simple Graph Undirected No No
Mutigraph Undirected Yes No
Pseudograph Undirected Yes Yes
Directed graph Directed No Yes
Directed multigraph Directed Yes Yes
//----------------------------------------------------------------------------
```

## Graph Terminology

### BASIC TERMINOLOGY

- Undirected Graph

--Two vertices $u$ and $v$ in $G$ are called`adjacent`

or`neighbors`

if $e=\left\{u,v\right\}$ is a edge of $G$.

--If $e=\left\{u,v\right\}$, the edge $e$ id called `incident with`

$u$ and $v$. The edge $e$ is also said to connect $u$ and $v$. $u$ and $v$ `endpoints`

.

--The `degree`

of a vertex in an `undirected graph`

is the number of the edges incident with it, except a loop at a vertex contribute twice to the degree of that vertex, denoted by $deg(v)$. **Isolated vertex:** $deg=0$. **Pendant vertex**: $deg=1$.

**Theorem:**(The Handshaking Theorem) If $G$ is a graph with $m$ edges and n vertices $v_1,v_2,...,v_n$, then

$$\sum_{i=1}^{n}deg(v_i)=2m$$

In particular, the sum of all the degrees of all the vertices of the graph is even. **example**: How many edges are there in a graph with 10 vertices each of degree 6? **solution**: $|e|=30$.

- Directed Graph

--When $(u,v)$ is an edge of the graph $G$ with directed edges. $u$ is said to be`adjacent`

to $v$ and $v$ is said wo be`adjacent`

from $u$.

$u$--

initial vertex, $v$--terminalorend vertex

The initial vertex and and terminal vertex of a loop are the same.

--The in-degree of a vertex $v$, denoted by $deg^-v$, is the number of edges with $v$ as their terminal vertex.

--The out-degree of a vertex $v$, denoted by $deg^+v$, is the number of edges with $v$ as their initial vertex.

(Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.) **Theorem:** Let $G=(V,E)$ be a graph with directed edges. Then

$$\sum_{i=1}^{n}deg^-(v_i)=\sum_{i=1}^{n}deg^+(v_i)=|E|$$

### SOME SPECIAL SIMPLE GRAPHS

1) Complete graph

The complete graph $K_n$ is the simple graph with n vertices and every pair of vertices is joined by an edge.

$K_n=(V,E),where E=\left\{\left\{u,v\right\}|u\neq v\right\}$ **Remark:** $|E|=C(n,2)$

2) Cycles

The cycle $C_n$, $(n\ge 3)$ consists of n vertices $v_1,v_2,...,v_n$ and edges $\left\{v_1,v_2\right\},\left\{v_2,v_3\right\},...,\left\{v_n-1,v_n\right\}$.

3) Wheels

We obtain the wheel $W_n$ when ew add an additional vertex to the cycle $C_n$, for $n\ge 3$, and connect this new vertex to each of the n vertices in $C_n$, by new edges.

4) $n$-Cubes

The $n$-Cubes, denoted by $Q_n$, is the graph that has vertices representing the the $2^n$ bit strings of length $n$.

5) Bipartite graph

A bipartite graph $G=(V,E)$ is a graph such that

$V=V_1\cup V_2$

,$V_1\cap V_2=\emptyset$

No edges exist between any two vertices in the same sub-set $V_k$, $k=1,2$.

**example:** $C_6$ is a Bipartite graph and $K_3$ is not bipartite.

**Definition:** A bipartite graph is the complete bipartite graph $K_{m,n}$ if every vertices in $V_1$ joined to a vertex in $V_2$ and conversely, $|V_1|=m,|V_2|=m$

### NEW GRAPH FROM OLD

**Definition:**$G=(V,E),H=(W,F)$

- $H$ is a
**subgraph**of $G$, if $W\subseteq V,F\subseteq E$ - $H$ is a
**spanning subgraph**of $G$, if $W=V,F\subseteq E$ - The
**union**of two simple graph $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is the simple graph with vertex set $V_1\cup V_2$ and edges set $E_1\cup E_2$. The union of $G_1$ and $G_2$ is denoted by $G_1\cup G_2$.

## Representing Graphs & Graph Isomorphism

There are many useful ways to represent graphs: Graph, adjacancy lists, adjacancy matrices and incidences.

**Adjacency Matrix**

Suppose that $G=(V,E)$ is a graph, where $|V|=n$. Suppose the vertices of G are listed arbitrarily $v_1,v_2,...,v_n$.

**Definition:** Let $G$ be a simple graph. The **adjacency matrix** $A={\lbrack a_{ij}\rbrack}_{n\times n}$ where $a_{ij}=$

$$ \left\{ \begin{matrix} 1 & if\{v_i,v_j\}\in E \\ 0 & otherwise \end{matrix} \right. $$

**Remark:**

1) The adjacency matrix of a simple graph is symmetric, that is $a_{ij}=a_{ji}$.

2) $a_{ii}=0(i=1,2,...,n)$since a simple graph has no loops.

3) $deg(v_i)=\sum_{j=1}^na_{ij}$

**Definition:** Let G be an undirected graph with loops and multiple edges. The **adjacency matrix** $A=[a_{ij}]_{n\times n}$ where

$a_{ij}=$ the number of edges that are associated with $\{v_i,v_j\}$

**Remark:** The adjacency matrices of all undirected graphs, including multigraphs and psedographs are symmetric.

**Definition:** Let $G$ be a **directed graph**. The adjacency matrix $A=[A_{ij}]_{n\times n}$ where $a_{ij}=$

$$ \left\{ \begin{matrix} 1 & if(v_i,v_j)\in E \\ 0 & otherwise \end{matrix} \right. $$

**Remark:**

1) The adjacency matrix of a directed graph does not have to be symmetric.

2) The adjacency matrix can also be used to describe a directed multigraph, where $a_{ij}=$ the number of edges that are associated to $(v_i,v_j)$.

**Incidence Matrix**

**Definition:** Let $G=(V,E)$ be an undirected graph. Suppose that $v_1,v_2,...v_n$ are the vertices and $e_1,e_2,...,e_m$ are the edges. Then the incidence matrix with respect to this ordering of $V$ and $E$ is matrix $M=[m_{ij}]_{n\times m}$ where

$$ m_{ij}= \left\{ \begin{matrix} 1 & {when\ edge\ e_i\ is\ incidence\ with\ v_i}\\ 0 & otherwise \end{matrix} \right. $$

**Remark:**

Incidence matrices can also be used to represent multiple edges and loops.

1) Mutiple edges $\Leftrightarrow$ columns with identicaL entries.

2) Loops $\Leftrightarrow$ columns with exactly entry equal to 1.

### ISOMORPHISM OF GRAPHS

**Definition:** Two simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are called **isomorphic**, if there is a bijection $f$ from $V_1$ to $V_2$ with the property

$$\forall a,b\in V_1,(a,b)\in E\Leftrightarrow(f(a),f(b))\in E_2$$

Bijection $f$ is called an isomorphism.

**Remark:**

1) It is difficult to determine whether two simple graphs are isomorphic.($n!$ possible bijection between two simple graphs with $n$ vertices)

2) We can show that two simple graphs are not isomorphic by showing that they not share the **invariant properties** under isomorphism, such as the same number of vertices, edges and the degrees of the vertices.

3) We can show that their adjacency matrices are the same, when the row and columns are labeled to correspond to the images under $f$ of vertices.

## Connectivity

### PATHS

**Definition:** A **path** of length $n(n\in Z^+)$ from $u$ to $v$ in an undirected graph is a sequence of edges $e_1,e_2,...,e_n$ of the graph such that

$$f(e_1)=\{x_0,x_1\},f(e_2)=\{x_1,x_2\},...,f(e_n)=\{x_{n-1},x_n\}$$

where $x_0=u$ and $x_n=v$.

- The path is a
**circuit**if it begins and ends at the same vertex. - A path or circuit is simple if it does not contain the same edge more than once.
- The graph is simple, we denote this path by its vertex sequence $x_0,x_1,...,x_n$.

**Definition:** A **path** of length $n(n\in Z^+)$ from $u$ to $v$ in a directed graph is a sequence of edges $e_1,e_2,...,e_n$ of the graph such that

$$f(e_1)=(x_0,x_1),f(e_2)=(x_1,x_2),...,f(e_n)=(x_{n-1},x_n)$$

where $x_0=u$ and $x_n=v$.

- The path is a
**circuit**if it begins and ends at the same vertex. - A path or circuit is
**simple**if it does not contain the same edge more than once.

### CONNECTEDNESS IN UNDIRECTED GRAPHS

**Definition:**

- An undirected graph is called
**connected**if there is a path between every pair of distinct vertices of the graphs. - When a graph that is not connected is the union of two or more connected subgraphs -- are called the
**connected components**.

**Therem:** There are a simple path between every pair of distinct vertices of a connected undirected graph.

**Proof:** Let $G=(V,E)$ be a connected undirected graph, $u,v\in V, u\neq v.$

$G$ connected $\Rightarrow \exists$ at least one path between $u$ and $v$. Let $u=x_0,x_1,...x_n=v$ be the vertex sequence of a path of **least** length.

Suppose it is not simple. Then $x_i=x_j$ for some $i$ and $j$ with $0\le i\le j$.

$\Rightarrow \exists$ a path from $u$ $v$ of shorter length with vertex sequence $x_0,...x_{i-1},x_j,...,x_n$ obtained by deleting the edges corresponding to the vertex sequence $x_i,...x_{j-1}$

**Definition:** The removal of a vertex and all edges incident with it produces a subgraph with more connected components than in the original graph. Such vertices are called **cut vertices**.

An edge whose removal produces a subgraph with more connected components than in the original graph is called a **cut edge** or **bridge**.

### CONNECTEDNESS IN DIRECTED GRAPHS

**Definition:**

- An directed graph is
**strongly connected**if there is a path from $a$ to $b$ and from $b$ to $a$ when ever $a$ and $b$ are vertices in the graph. - An directed graph is
**weakly connected**if there is a path between any two vertices in the underluing undrected graph.

**Remark:** Strong connected $\Rightarrow$ Weakly connected

### COUNTING PATHS BETWEEN VERTICELS

**Theorem:** Let $G$ be a graph with adjacency matrix $A$ wwith respect to the ordering $v_1,v_2,...,v_n$. The number of different paths of length $r$ from $v_i$ to $v_j$, where $r$ is a positive integer, equals to the $(i,j)$th entry of $A^r$.

**Proof:** (By mathematical induction)

1) Let $G$ be a graph with adjacency matrix $A$ (Assuming an ordering $v_1,v_2,...,v_n$ of the vertices of $G$). The number of paths from $v_i$ to $v_j$ of length 1 is the $(i,j)$th entry of $A$.

2) Assume that the $(i,j)$th entry of $A^r$ is the number of different paths of length $r$ from $v_i$ to $v_j$.

$$A^{r+1}=A^rA$$

--the $(i,j)$th entry of $A^{r+1}$ equals

$$b_{i1}a_{1j}+b_{i2}a_{2j}+...+b_{in}a_{nj}$$

where $b_{ik}$ is the $(i,k)$th entry of $A^r$ ($b_{ik}$ is the number of paths of length r from $v_i$ to $v_j$).

A path of length $r+1$ from $v_i$ to $v_j$ is made up of a path of length r from $v_i$ to some intermediate vertex $v_k$, and an edge from $v_k$ to $v_j$.

$$\sum_{k=1}^n b_{ik}\cdot a_{kj}$$

these products are addred for all posiible intermediate vertices $v_k$, the desired result follows the sum rule for counting. **Remark:** Theorem can be used to determine whether a graph is connected.

## Euler and Hamilton Paths

### EULER PATHS AND CIRCUITS

**Definition:** An **Euler circuit** in a graph $G$ is a simple circuit containing every edge of $G$. An **Euler path** is a simple apth containing every edge of $G$.

A graph $G$ is an $G$ is an **Euler Graph** if it has an Euler circuit.

**Theorem:** (Necessary and Sufficient Condition) A connected multigragh $G=(V,E)$ has an Euler circuit if and only if

- Every vertex in the graph havs even dege. (the $deg(v_i)$ must be even)

**Proof:** "$\Rightarrow$"

$G$ has a euler circle $\Rightarrow$ $G$ connected: trival

$G$ has a euler circle $\Rightarrow$ Every vertex in G has even degree

Consider $v\in V$. Suppose $v$ visites $k$ times by the Euler circuit, every visit use 2 new degree (in and out).

Hence,$deg(v_1)$ is even. **Proof:** "$\Leftarrow$"

Take any $v_0\in V$.

- Consider any path $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \neq v_0$

$deg(v_k)$ is even

$v_k$ has an odd number of visited edges

$\Rightarrow v_k$ has an unvisited edge

Extend path $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_{k+1}$

Repeat until $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_m=v_0$

- Consider circuit $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_m=v_0$

Suppose some $v_k$ has unvisited edge to $v_{m+1}$. By symmetry, let $v_k=v_0$

Extend path $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_m=v_0\rightarrow v_{m+1}$

Repeat until $v_i$ has no unvisited edges.

$G$ connected $\Rightarrow$ all edges in $E$ visited

Therefore, $G$ has a Euler circuit.

**Theorem:** A connected multigraph $G=(V,E)$ has an Euler path but not an Euler circuit if and only if

- has exactly two vertices of odd degree

### HAMILTON PATHS AND CIRCUITS

**Definition:** A path $x_0,x_1,...,x_{n-1},x_n$ in the graph $G=(V,E)$ is called a **Hamilton path** if $V=\{ x_0,x_1,...x_{n-1},x_n\}$ and $x_i\neq x_j$

A circuit $x_0,x_1,..,x_{n-1},x_n,x_0$ (with $n>1$) in a graph $G=(V,E)$ is called a **Hamilton circuit** if $x_0,x_1,..,x_{n-1},x_n$ is a Hamilton path.

If a connected graph $G$ has a Hamiltonian circuit, $G$ is called a Hamilton graph.

**Remark:** A Hamilton circuit in a graph $G$ is a circuit which visited every vertex in $V$ exactly once.

**Theorem:** If $G$ is a connected simple graph with $n$ vertices where $n\geq 3$, then $G$ has a Hamilton circuit if the degree of each vertex is at least $n/2$.

**Remark:** The best algorithms known for finding Hamilton circuit in a graph or determing that no such circuit exists have exponential worst-case time complexity.

本文由 Rust401 创作，采用 知识共享署名4.0 国际许可协议进行许可

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名

最后编辑时间为: Mar 28, 2019 at 03:38 am

Sildenafil Citrate Tablets generic viagra Cialis 5 Prezzo Meilleure Facon De Prendre Priligy

http://northwestpharmaciescanadian.com - canadian pharmacy meds review how to find a doctor canadian pharmacy online no prescription health

sertraline is the identify as a replacement for the treatment of erectile dysfunction. This generic hallucinogenic is very much noticeable in treating impotence. Tadalafil is the essential ingredient of medications. http://zoloftmedication.com what are the side effects of zoloft was oldest manufactured by means of Ranbaxy. This downer works on all men irrespective of any originator or duration of the quandary and the age. November 9, 2016 16:54

http://canadianpharmacyjud.com - canadian online pharmacies prescription drugs canada drugs online reviews

Mild side effects of online canadian pharmacy are blur perspective, color blindness, acid upset stomach, hearing loss, diarrhea, pain in the neck, nasal congestion, urinary quarter infections, reddening of phizog, dizziness, etc. These are low-grade fallouts and disappear on own. Chiefly these symptoms materialize to men unique to this drug. Keep an eye on compelling the http://safemedsxl.com canadian pharmacy tied if they enter someone's head and as your body intention become traditional to it wish discontinue occurring at all. Yes, if these effects continue fit protracted in days of yore, then notify your doctor promptly. November 15, 2017 3:57

http://viagrapills.us.org - generic viagra names specialist physician viagra generic

Safeguarding measures are must to be followed beforehand taking viagra without doctors prescription. They persuade of treatment refuge and increase confidence in the drug. To begin wary move to be bewitched is to take hold of the http://overcounteronline.com buying viagra in mexico over the counter on direction solely. Even if handy without medication also, but take after thriving through complete medical examination. December 4, 2017 15:56