Graph
in Discrete Mathematics with 7 comments

Graph

in Discrete Mathematics with 7 comments

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

Graph

Introduction to Graphs

Definition:

Remark:
To summarize,

Definition:

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

--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$.
 

$u$--initial vertex , $v$--terminal or end 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)$


Representing Graphs & Graph Isomorphism

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


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)$.


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$.



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$.


CONNECTEDNESS IN UNDIRECTED GRAPHS


Definition:


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:


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


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$.

$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$

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


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.


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

    Reply
    1. @StevRing

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

      Reply
    2. @StevRing

      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

      Reply
    3. @StevRing

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

      Reply
    4. @StevRing

      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

      Reply
    5. @StevRing

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

      Reply
    6. @StevRing

      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

      Reply