graph_basics

This course goes through graph theory basics we shall need in further chapters. You should come back to this chapter when needed to check for definitions and basic properties.

- A graph is an ordered pair where denotes the set of
*vertices*, or*nodes*of the graph and denotes its set of*edges*or*links*. - Edges of a graph connect two nodes.
- An edge may be
*directed*, in which case we write as an*ordered pair*of nodes. Nodes and are then called the*source*and*destination*(or*target*) nodes. The set*E*is then a subset of the Cartesian product . - An edge may unordered, in which case we write as an
*unordered*pair (a subset of two elements). The set is then a subset of (all subsets of of cardinality 2).

- When edges of a graph are directed, the is said to be a
*directed graph*. Otherwise, the graph is said to be*undirected*. - A
*loop*is an edge where the source and target nodes coincide. Note that a loop is denoted as a pair in a directed graph while a loop in an undirected would correspond to a singleton (note also that this requires that we extend to be a subset of ). - A node is a
*neighbor*of a node if there is an edge . Neighbors of a node define its*neighborhood*denoted as or simply . Neighbors in a directed graph divides in two subsets and depending on whether edges connecting nodes to are*outgoing*(looking at things from 's perspective) or*incoming*, respectively, with . - The
*degree*of a node is the cardinality of its neighborhood. Nodes of a directed graphs have an*out degree*and*in degree*as well.

- A graph is a
*subgraph*of a graph if and are subsets of and , respectively. - A subgraph is an
*induced subgraph*if contains all possible edges between nodes in that appear in . That is, .

- A (simple and undirected) graph is said to be
*complete*if it contains a maximum number of edges, namely . - A
*clique*of a graph is an induced subgraph which happens to be complete. - A graph is said to be
*bipartite*if its nodes may divided into two distinct subsets such that no edge connect any two nodes and . - A graphs said to be
*bipartite and complete*if it contains a maximum number of edges while being bipartite, in which case it contains precisely edges.

** Exercises / Assignments **

- Design an algorithm that, given a subset of nodes , computes the induced subgraph on .
- Design an algorithm that tests whether a subgraph is an induced subgraph.
- Can you design an algorithm that tests whether a subgraph is a clique.
- Can you design an algorithm that tests whether a subgraph is bipartite; bipartite and complete.

We shall be mainly concerned with undirected graphs. Some definitions allow for edges to appear multiple times in a same graphs – these special types of graph are called *multigraphs* (but we will not consider them in this course). Graphs where edges appear at most once are called *simple* graphs.

- A
*path*in a graph is given as a sequence of nodes where pairs correspond to edges of the graph (note that we didn't specify whether edges were directed or not). Nodes and are then said to be*connected*. - The
*length*of a path is , that is the number of edges it traverses. - A path is
*simple*is if*does not include the same edge twice*(not that does not forbid to cross the same vertex more than once). - A path is
*elementary*if it*does not go through the same vertex twice*(note that*elementary paths necessarily are simple*). - A
*cycle*(in a simple undirected graph) / a*circuit*(in a directed graph) is a path that starts and ends at the same vertex.

Here are the first simple graph properties that nevertheless turn out to be essential.

- A undirected graph is
*connected*if any two nodes are connected by a path. - A directed graph is
*weakly connected*if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is*connected*if it contains a directed path from to or a directed path from to for every pair of vertices . It is*strongly connected*if it contains a directed path from to*and*a directed path from to for every pair of vertices . - A
*connected component*of a (directed or undirected) graph is a connected maximal induced subgraph of (maximal with respect to set inclusion). - Undirected graphs additionally allow to define weakly and strongly connected components.
- Because connected are maximal, graphs have a unique decomposition into connected components (or weakly/strongly components for undirected graphs).

** Exercises / Assignments **

- Can you prove the last assertion claiming the existence and uniqueness of graph decomposition into connected components (and weakly/strongly components for undirected graphs).
- Can you think of an algorithm to test whether a path exist between two nodes? (without using a side data structure but solely marking nodes)
- Can you think of an algorithm to test whether a graph is connected? (without using a side data structure but solely marking nodes)
- What would be the time complexity of these algorithms?

*Trees* are quite special graphs, which turn out to be essential in computer science and in graph visualization as well.

- A
*tree*is a simple undirected graph that is both*connected and cycle free*. These conditions have a number of consequences:

- In any tree , for any two nodes there is a unique path connecting them.
- The number of edges in a tree is one less than its number of nodes.

- Trees are sometimes considered to be directed graphs, with a special node called the
*root*of the tree, with the special requirement that for any node u there is a unique (directed) path from to . That is, all edges point outwards from and any node is reachable from . Observe that in a simple undirected tree, choosing a node as root implicitly defines the orientation of all edges so that they point outwards from the root.

Connectedness is awfully useful and extends into a bunch of variations.

- A simple undirected graph is
*biconnected*if for any two nodes, there exist two distinct paths connecting them. That is, there are two ways to go from node to node , for any two nodes . - Let be a connected graph. An
*articulation point*in is a node such that deleting disconnects . That is, has more than one connected components.

** Exercises / Assignments **

- Prove the following claim: a graph is biconnected if and only if it has no articulation point.
- Prove the following corollary (consequence of the preceding claim): a graph uniquely decomposes into biconnected components.

A *partition* of a set is a collection of subsets such that , that is, any node in is contained in exactly onde subset . The subsets are usually called *clusters*. The partition is sometimes denoted as .

Given a graph and a partition , we define the *quotient graph* as a graph whose nodes correspond to the subsets and where edges are induced from edges in . More precisely, there is an edge between nodes and in if and only if there is at least one edge connecting a vertex from to a vertex in .

- Coming back to the decomposition of a graph into biconnected components. Biconnected components of a graph provide a partition of . Show that the quotient graph is a tree.

Being able to efficiently/astutely going through all nodes and/or edges of a graph is an essential ingredient of any graph algorithm. There are two main strategies to do so. Any search needs a seed node from which to start. Graphs are assumed to be connected, otherwise each component needs to be visited separately.

Breath first search (BFS) given a seed node u put it in a queue while the queue is not empty grab a node from the queue mark it as visited and delete it from the queue enqueue its neighbors (if they are not already in the queue)

Depth first search (DFS) given a seed node put it on a stack while the stack is not empty grab a node from the stack delete it from the stack put its neighbors on the stack (if they are not already in the stack)

Because nodes are seen only once during these traversals (because are stored only when they are first “seen”), these traversals define trees obtained by selecting edges used to reach neighbors before they are stored.

** Exercises / Assignments **

- Implement DFS and BFS under Tulip, using the python view and node attributes to exhibit DFS and BFS order (have nodes oscillate a bit when they are visited for instance, or color them on a red to blue scale according to the order of visit).
- Show that the edges traversed by a DFS or BFS indeed defines a tree.
- Select a seed node and traverse the graph using DFS. Show that a node is an articulation point if and only if has degree at least 2 in the tree built from the DFS traversal.

- Among all paths connecting two nodes and some have a shortest length shortest (and thus they necessarily are elementary). The length of a shortest path between nodes and defines the
*distance*between and . - The distance function is indeed a distance, that is it satisfies
*positivity*,*symmetry*and the*triangular inequality*. - Note that defining the distance function only makes sense for undirected graphs (otherwise we loose symmetry).
- The distance function is easily computed in a tree because paths are unique.

- Computing the distance function relies on Dijkstra's algorithm computing distance from a given node . Values are obtained by running a DFS from . The distance from are then obtained from the lengths of paths from in . This requires to run Dijkstra's algorithm from each node in .
- The distance computation problem is known as the
*single source shortest path problem*, and admits a number of variations and improvements (for weighted graphs, undirected, etc.). See the wikipedia pages, for instance.

Most often edges may be equipped with real values called edge *weights*. We may also occasionally consider node weights. That is, we have function (and/or ). Weights allows for a definition of a node's *weighted degree*, that is the sum of weights of edges connecting a node to its neighbors .

The *weight of a path* (or *weighted length*) can similarly be redefined as the sum of weights of edges connecting nodes along the path, leading to the definition of a *weighted distance* as well (which as a matter of fact may well fail to be a distance in the strict mathematical sense). Dijkstra'a algorithm may be tuned to take weights into account and find paths of minimal weights. This requires to define traversals taking decisions according to weights of edges as they are traversed or reached (impacting the order in which nodes are enqueued, for instance).

** Exercises / Assignments **

- Browse the literature (wikipedia again) to find algorithms computing weighted distance between nodes of a graph. Implement them under Python using Tulip's python view, for instance.
- Think of a number of ways weights may be defined on quotient graphs (computed on weighted graphs).

This notion is fundamental to graph theory, and the basic idea is quite simple: find a tree that spans the whole network – note that this only makes sense if the graph is connected other wise you would get a tree for each of the connected component ending up with a *forest*.

Now, the basic trick to build a tree is easy: start for any node and traverse the graph while marking those edges that form a tree. Stop when you finally reached all nodes.

queue Q // used to store nodes as they are visited hashmap visited // used to mark nodes as visited start node n tree T = (V_T, E_T) (with V_T = {} and E_T = {} are empty) mark all nodes as not visited enqueue n V_T <- V_T + n (add node n to T) while Q is not empty n = dequeue Q loop over all neighbors u of n enqueue u if not visited V_T <- V_T + u E_T <- E_T + (n, u) (add node u and edge n-u to T)

Now, a number of variations can be designed in order to satisfy specific criteria. This is particularly useful when dealing with weighted graphs. For instance, computing a spanning tree with minimum (total) weight.

*Prim's algorithm* solves the problem of finding a minimum spanning tree (borrowed from Wikipedia).

Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative) Initialize: T = (V_T = {x}, E_T), where x is an arbitrary node (starting point) from V, and E_T = {} Repeat until V_T = V: Choose an edge (u, v) with minimal weight such that u is in V_T and v is not (if there are multiple edges with the same weight, any of them may be picked) Add v to V_T, and (u, v) to E_T Output: T = (V_T, E_T) is a minimal spanning tree

Kruskal's algorithm follows a quite ifferent strategy to solve the minimum spanning tree problem.

create a forest F (a set of trees), where each vertex in the graph is a separate tree create a set S containing all the edges in the graph while S is nonempty and F is not yet spanning remove an edge with minimum weight from S if that edge connects two different trees, then add it to the forest, combining two trees into a single tree otherwise discard that edge At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph

** Exercices / Assignments **

- When edges in a graph all have distinct weights, the minimum spanning tree is unique.
- Wikipedia's page on Prim's algorithm lists time complexity of the algorithm depending on the data structure used to store the graph. Explain.
- Samething with Kruskal's algorithm.
- Implement these two algorithms using python and Tulip. Animate the algorithm so we van visually follow how the algorithms proceed.

—

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/graph_basics.txt · Last modified: 2016/03/10 13:59 by melancon