# Graphs/Definitions

### From charlesreid1

## Contents

## Dietel Chapter 1: Graph Definitions and Concepts

Outline:

- Definitions
- graph,
- degree,
- path,
- cycle,
- connectivity,
- tree, forest,
- k-partite,
- contraction,
- Euler tours

### Graph definitions

A **graph** G consist of a set of nodes (vertices) V and edges E, denoted

**Vertex set** on graph G is denoted

**Edge set** on graph G is denoted

Number of vertices in a graph is called the **order** and is denoted

Number of edges in a graph is denoted

Vertex and edge are **incident** if the edge connects to the vertex.

Set of all edges at a particular vertex v is denoted

Two vertices x, y are **adjacent** on a graph if there is an edge with endpoints x and y

If all vertices are pairwise adjacent, the graph is **complete**

For two graphs and , the graphs are isomorphic if there exists a biijection from G to G'.

If we have two graphs G and G', we say that G' is a subgraph of G if all V' subset of V and all E' subset of E

A subgraph G' is a **spanning subgraph** of G if all V' span all of G (if V' = V)

### Degree definitions

Set of neighbors of a vertex v is denoted

Degree of a vertex v is denoted and is equal to the number of edges at v

Vertex of degree 0 is **isolated**

A graph G where all of the vertices have the same degree, k, is called **k-regular** (or, just **regular**).

The vertex on the graph with the smallest degree is the **minimum degree of G**

The vertex on the graph with the largest degree is the **maximum degree of G**

The average degree of G is given by the expression

Ratio of edges to vertices on a graph is

If we define edges as having two endpoints, then adding up the degrees of all vertices will lead to twice the number of edges. Mathematically:

This leads to the identity and the theorem that the number of vertices of odd degree in a graph must always be even. Contrawise proof: if the number of vertices of odd degree is odd, the number of edges is not be an integer.

### Path and Cycle Definitions

A path P on a graph G is a non-empty graph that contains vertices and edges that are in G: and

A path is usually referred to by the sequence of vertices it visits, or as a path "from/between x1 to xk"

**Independent paths** are paths containing no common (internal) vertices. Independent paths may share endpoints though.

We can denote parts of a path using special notation: if a path , then the following notation is used to denote only a part of that path:

We can also connect paths using unions, or by using more shorthand:

A **cycle C** consists of a path whose final edge connects the last node to the first node. Given a path the cycle is then

A k-cycle is denoted and is a cycle of length k.

The girth of a cycle is the number of edges or vertices in a cycle in a graph G. The circumference of a graph is the maximum length of a cycle in a graph G.

The distance of two vertices x and y is the length of the shortest path from x to y .

A vertex is **central** if greatest distance from any other vertex is as small as possible. This minimum distance is the radius of the graph G. Formally:

Note that the radius of a graph is different from the minimum/average degree.

### Connectivity

A graph is **connected** if any two arbitrary vertices are connected.

If the graph is directed, a connected graph means that for any two arbitrary vertices u and v, there is an edge connecting u to v or v to u. A **strongly connected** graph means that for any two arbitrary nodes u and v, there is an edge connecting u to v and another edge connecting v to u.

Suppose we have two sets of vertices A and B, and a third set of vertices X. Further suppose that any path that connects a vertex from A to a vertex from B contains a vertex from X. Then we say that X **separates** the vertex sets A and B.

A subgraph of G that is maximally connected (contains every vertex in G) is a **component** of G. If a component is connected, it is always non empty.

Vertex connectivity: A graph G is **k-connected** if it has more than k vertices and if no two vertices of G are separated by fewer than k vertices. The maximum value of k such that G is k-connected is the **connectivity** of G and is denoted .

Edge connectivity: A graph G is **l-edge-connected** if every vertex is connected with fewer than l edges (this is a bit unclear). The edge connectivity is denoted .

Theorem due to Mader 1972: Every graph of average degree at least 4k has a k-connected subgraph. (Can prove inductively.)

### Trees and Forests

Acyclic graphs are called forests. Connected forests are called trees.

A connected graph with n vertices is a tree if and only if it has n-1 edges.

We can (but don't have to) pick a particular node to be special - the root of the tree. In that case it is a rooted tree. When we pick a root, this imposes an ordering (assuming vertices can be compared). Given two nodes x and y, we say that .

A rooted tree T is called normal if any two vertices that are adjacent in the graph are comparable. Every graph has a normal spanning tree.

### Bipartite Graphs

A **k-partite** graph is a graph where the set of vertices V can be partitioned into k classes, such that every edge that starts in one partition will end in a different partition.

If we can select any two vertices from two different classes and they are connected, the k-partite graph is **complete**.

Bipartite graphs cannot contain cycles of odd lengths. This is always true, so that we can identify bipartite graphs using this property: a graph is bipartite iff it contains no odd cycle.

### Edge Contraction

Given a graph G with vertex set V and edge set E. Let e be an edge connecting vertex x to vertex y. Then denotes the graph obtained by contracting the edge into a new vertex, which is now adjacent to all former neighbors of x and y.

### Euler Tours

An Euler tour is a closed walk on a graph that traverses each edge of the graph exactly once. Some graphs have an Euler tour (and are called Eulerian), other graphs are not.

A connected graph is Eulerian if and only if every vertex has even degree. This is because any vertex appearing k times in an Euler tour must have degree 2k.

### Other Definitions

A hypergraph is a pair of disjoint sets (V,E) where the elements of the edge sets are non-empty subsets of V. (That is, a given edge e in the set E can connect multiple vertices.)

A directed graph is a pair of disjoint sets (V,E) along with two maps: the init map from V to E (denoting the initialization or origin of the directed edge) and the term map from V to E (denoting the termination of the directed edge).

A multigraph is a pair of disjoint sets (V,E) together with a map from E to V or to V^2. In other words, it is a graph in which we can have edges that begin and end at the same vertex.

## Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |