Dietel Chapter 1: Graph Definitions and Concepts
- tree, forest,
- Euler tours
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)
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.
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.
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.
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.
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.
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.
Graphsnotes on graph theory, graph implementations, and graph algorithms
Part of Computer Science Notes
Series on Data Structures
Flags · Template:GraphsFlagBase · e
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e