Graphs: Eulerian and Weighted
|
|
A graph has a set of vertices and a set of edges which connect pairs of vertices. We began by exploring Pancoska's Eulerian Graph. An Eulerian graph is a graph which has an Eulerian circuit. An Eulerian circuit is an Eulerian path which starts and ends at the same vertex. An Eulerian path is a walk on the graph edges which uses each graph edge exactly once. There is a theorem that states that an undirected graph where each vertex has an even degree is Eulerian. The following is a Eulerian graph. Can you find the Eulerian circuit?
|
|
|
The following is a construction of an Eulerian graph from an siRNA sequence, call it S. The vertices are the C,G,A,U nucleotides. We create an edge for each (S[i],S[i+1]) pair where S[i] is the tail and S[i+1] is the head of the edge. We also create an edge from the last nucleotide in the sequence to the first nucleotide.
|
|
|
Starting from the directed graph above, we construct a weighted undirected graph by replacing multiple edges between a given pair of vertices by one edge labeled with a number representing the number of edges between those two vertices. The weighted graph of the above graph is shown below.
|
|
|
next
|