## Define

A graph consists of a set of nodes V and a set of edges E.

- Each edge in E joins two nodes in V
- Two nodes connected by an edge are called
**neighbors**or**adjacent**

**Edge**

**undirected**: can be traversed in both directions: When there is only one edge connecting two nodes x and y`{x,y}`

,`edge xy`

**simple graph**

the graph which has neither multiple edges nor loop edges

## Degrees

the degree of a node `v`

is the number of edges which have v as an endpoint. Represent by `Deg(v)`

- if self loop, count twice

For example,`deg(a)`

= 2,`deg(b)`

= 6,`deg(d)`

= 0

The relation between edge number and degree is

$$ \sum_{v\in V}deg(v)=2|E| $$

## Type of graph

Several special types of graphs that are useful

### 1. Complete graph

every node is connected to every other node,l represent by $K_i$ where `i`

represent the node number

the above complete graph is $K_5$

the edge of it equal to:

$$ \text{edge} = \frac{n(n-1)}{2} $$

### 2. Cycle graphs

all nodes and edges connecting vi to vi+1, plus an additional edge from vn to v1. where as v represent each single nodes in the graph.

the above cycle graph is $C_5$

$$ \text{edge}= n $$

- the cycle graph $C_n$ contains
*2n*different cycles (different start)

### 3. Wheel

cycle + an external hub, represent by $W_i$ where `i`

is the node number - 1

the above wheel represent by $W_5$

- $W_n$ has $n+1$ node

$$ \text{egde}=2n $$

## Isomorphism

Suppose $G(V_1,E_1)$ and $G_2(V_2,E_2)$ are graphs, an **isomorphism** means $G_1$ to $G_2$ is a bijection $f : V_1 \to V_2$

if there is an isomorphism from $G_1$ to $G_2$, then, we can say they are **isomorphic**

the above graph is isomorphic because we can map 1 to d, 2 to a, 3 to c and 4 to d

- isomorphism is another example of an equivalence relation

**Check NOT isomorphism:**

If not satisfied:

- same number of nodes and the same number of edges.
- same number of nodes of degree k

If the two property are identical, we should notice on their subspace. If two graphs G and F are isomorphic, **then any subgraph of G must have a matching subgraph somewhere in F**.

Subspace: If G and G′ are graphs, then G′ is a subgraph of G if and only if the nodes of G′ are a subset of the nodes of G and the edges of G′ are a subset of the edges of G

the left graph has $C_3$ as a subspace but right graph does not.

## Walks, paths, and cycles

**Walk: **sequence of node or edge from one node to another node

- shortest walk is zero (single node)
- the walk is
**closed**if its start and end are the same, otherwise it's**open** - can be more than one

**Path: ** a walk in which no node is used more than once

**cycle**is a closed walk with**at least three nodes**in which**no node is used more than once**except that the starting and ending nodes are the same- cycle diff from close walk that close walk can re-use node
**acyclic**means does not contain cycle in graph- can create a path between the nodes by pruning unnecessary loops from the walk.
- can be more than one

## Distances

distance from a to b means the length of **the shortest path** from a to b

**diameter**of a graph is the max**distance**between any pairs of nodes

diameter above is 4 since $d(f,e)=4$

## Connectivity

A graph G is connected if there is a walk between **every pair of nodes** in G

Not connected because no walk from a to g

**connected components: **some subset in a graph that each contains a maximal set of nodes that are all connected to one another. The graph above has three connected components

**cut edge**: if a connected graph become disconnected by removing a single edge, this edge is cut edge

## Euler circuits

a **closed walk** that uses each edge of the graph **exactly once**

**Check is Euler circuits**

- the graph is connected
- each node has
**even**degree

## Bipartite graphs

A graph G = (V, E) is bipartite if we can split V into two non-overlapping subsets V1 and V2 such that every edge in G connects an element of V1 with an element of V2

all R and all G nodes in this graph is not connected with themselves, but connect with each other,o so, it is bipartite graph

**Complete bipartite graph: **

- bipartite graph + each subsets are completed connected
- represent by $K_{m,n}$ where m and n represent node in each subsets

complete bipartite graph: $K_{3,2}$

$$ \text{node}=m+n $$

$$ \text{edge}=mn $$

本文作者：TwinIsland

版权声明：所有文章除特别声明外均系本人自主创作，转载及引用请注明出处