In this section we learn about

connectivity. Connectivity is one of the basic concepts of graph theory. We start by the formal definition of a path.

A path is a sequence of edges that begins at the vertex of the graph and

travels along the edges of the graph, always connecting pairs of adjacent vertices.

Depending on the

context, path length may either be the number of edges on the path, or the sum of the weights of the edges on the path.

For example, in this graph we have a path from 1 to 8 with length of 4.

Here is the same path but with an unweighted graph and the length is 20.

And here is another path from 1 to 8 in the same graph. Since graph may have more than one path between two vertices,

we may be interested in finding a path with a particular property.

For instance, find a path at minimum length.

The geodesic distance, or simply distance, from u to v in graph G, is the length of the shortest path from u to v in G.

We cannot always find the path between every two nodes of the graph.

Consider this graph. There is no path from 2 to 9.

The basic idea of connectivity is reachability among vertices of a graph by traversing its edges.

This can be defined formally and categorized in five types: Path where no vertex can be repeated,

Trail where no edge can be repeated,

Walk where there is no restriction,

Circuit is a closed trail, and cycle is a closed path.

We call a graph cyclic if it contains any cycle. Otherwise we call it acyclic graph.

An undirected graph is connected if there is a path between every pair of its vertices.

The directed graph is strongly connected if there is a path from A to B and from B to A

whenever A and B are vertices in the graph. A directed graph is weakly connected if there is an

undirected path between every two vertices in the graph.

Which graph is more strongly connected, G1 or G2?

True, G1 is more strongly connected.

A strongly connected graph can be weakly connected but the vice-versa is not true. Do you know why?

Here is an example of a not-connected graph. How you can make it connected?

Yes, by adding an edge between 5 and 9

you can make the graph connected. This concept, the minimum number of elements,

nodes, or edges that need to be removed to disconnect the remaining nodes from each other in a graph, is an

important measure in studying the resilience capacity of a network.

The maximal subgraph that is connected in a graph is called the connected component. Note that we cannot add

vertices and edges from the original graph to the component and retain its connectedness because it is maximal.

So then it is clear that a connected graph has exactly one component.

So let's look at one of the graphs we had before to see how many components does it have.

It has two connected components. Is the graph connected?

In this graph, the part separated by the blue line is not a connected component. Do you know why?

If a graph is cyclic, the removal of an edge that is on a cycle does not affect connectedness of the graph.

Therefore a connected subgraph with all vertices and minimum number of edges has no cycles.

Looking for cyclic subgraphs traces back to

1735 when the Swiss mathematician Euler saw the Koenigsberg bridge problem.

The Koenigsberg bridge problem was an old puzzle concerning the possibility of finding a path over

every one of the seven bridges that span a forked river flowing past an island

but without crossing any bridge twice.

What Euler realized was the most of information on the map had no impact on the answers to the questions.

By thinking of each bank and island as a vertex and each bridge as an edge joining them,

Euler was able to model the situation using the graph you can see on the right hand side.

Euler argued that no such a path exists. This proof involved only references to the physical arrangement of the bridges

but essentially he proved the first theorem in graph theory.

We say graph G has Euler cycle

if and only if every vertex of G has an even degree.

A connected graph G has an Euler trail from node a to some other node b

if and only if G is connected and a is not equal to b, are the only two nodes of odd degree.

One of the important classes of graphs is the trees.

The importance of trees is evident from their application in various areas, especially

theoretical computer science and molecular evolution.

A tree is a connected graph without any cycle, or equivalently a tree is a connected

acyclic graph.

Do you remember what acyclic means a?

Graph having no cycle is said to be acyclic or also can be called forest.

It follows immediately from the definition that a tree has to be a simple graph and has a unique simple path

connecting each pair of its vertices.

There are alternative methods for defining the tree.

Any connected subgraph of an acyclic graph is a tree. The graph is a tree if adding an edge between two vertices

creates a cycle and removing any edges disconnects the graph.

We can list more properties of the trees.

The number of vertices is one larger than the number of edges, or a tree with at least two vertices

has at least two vertices of degree one.

Sometimes we are given a graph but you only need one way to connect the nodes.

For example a network with redundant connections. When you are routing data, you don't care about redundancy,

you just need a way to send the data to its destination.

So if you're looking at routing decisions,

you basically want to reduce the graph to a tree. The tree tells us exactly how we will send the data.

Given a graph G, a subgraph of G that connects all

vertices of G and is a tree, is called a spanning tree of G.

The spanning tree of a graph contains the minimum number of edges to keep the graph connected.

An algorithm

used to construct a spanning tree is non-deterministic in two ways: the choice of vertex u is

arbitrary, the choice of the edge incidence on u to add to the tree is arbitrary.

Therefore we can have more than one spanning tree for each graph.

Consider the following graph. Can you find one of its the spanning trees?

Here is one spanning tree of the graph.

Here is another spanning tree of the same graph.

Prime's algorithm and Kruskal's algorithm are often used to construct a spanning tree.

There are greedy algorithms that run in polynomial time.