Here in this blog, we are asked to describe the Peterson graph problem. The Petersen graph is an undirected graph in the study of graph theory that has 10 vertices and 15 edges. It is a short graph that may be used as both a counterexample and an example for a variety of graph theory issues. Julius Petersen built the Petersen graph in 1898 with the goal of making it the smallest bridgeless cubic graph without three-edge coloring. In the Peterson graph problem, graph G known as a Petersen graph is given to us, and its vertices are numbered from 0 to 9. The vertices of G will also receive some letter assignments. Let us understand this with a proper example.

Sample Example

Consider the graph given above as G. The graph given is the Peterson graph. The vertex numbers range from 1 to 10. Letters will be present on each vertex. Let's take a look at one walk W in the graph with L vertices. When the letter sequences in W and S are the same, the walk W realizes a string S with L letters. The vertices are accessible many times. For instance, the walk method reveals that one string S is similar to "ABBECCD" (0, 1, 6, 9, 7, 2, 3). Finding such a walk is our task, followed by finding the lexicographically least such walk if it already exists. Return -1 if there is no suck walk.

Suppose if we take S= ”ABB”, then the output will b 016. Because we can clearly see in the graph that the path from ABB is 016.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Algorithm

We will implement the petersonGraphWalk(S, v) function:

Step 1: We will take a res variable and initialize it with res:= starting vertex

Step 2: Now for each character c in S except the first one, we will check if there is an edge between v and in the outer graph, if the edge is present then:

v := c

Step 3: Else if there is an edge present between v and c+5 in the inner graph, then

We will calculate v := c + 5

Step 4: If both conditions are not satisfied, we will return false.

Step 5: Put v into the res variable.

Let us see the implementation of this approach in the next section of this blog.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
char path[100005]; //path which needs to be checked
bool adj[10][10]; // adjacency matrix of the path
char res[100005]; // resulted path
bool petersonGraph(char * path, int v) //BFS
{
res[0] = v + '0';
for (int i = 1; path[i]; i++) {
// first traverse the outer graph
if (adj[v][path[i] - 'A'] || adj[path[i] -
'A'][v]) {
v = path[i] - 'A';
}
// then traverse the inner graph
else if (adj[v][path[i] - 'A' + 5] ||
adj[path[i] - 'A' + 5][v]) {
v = path[i] - 'A' + 5;
} else
return false;
res[i] = v + '0';
}
return true;
}
int main() {
// representation in adjacency matrix
adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] =
adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] =
adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] =
adj[9][6] = adj[6][8] = adj[8][5] = true;
char path[] = "ABBECCD"; //path which needs to be checked
if (petersonGraph(path, path[0] - 'A') ||
petersonGraph(path, path[0] - 'A' + 5)) {
cout << res;
} else {
cout << "-1";
}
return 0;
}

Output

The path is: 0169723

Implementation in Java

class Graph {
static char[] path = new char[100005]; //path which needs to be checked
static boolean[][] adj = new boolean[10][10]; // adjacency matrix.
static char[] res = new char[100005]; // resulted path
static boolean petersonGraph(char[] path, int v) //BFS
{
res[0] = (char)(v + '0');
for (int i = 1; i < (int) path.length; i++) {
// first traverse the outer graph
if (adj[v][path[i] - 'A'] ||
adj[path[i] - 'A'][v]) {
v = path[i] - 'A';
}
// then traverse the inner graph
else if (adj[v][path[i] - 'A' + 5] ||
adj[path[i] - 'A' + 5][v]) {
v = path[i] - 'A' + 5;
} else
return false;
res[i] = (char)(v + '0');
}
return true;
}
public static void main(String[] args) {
// representation in adjacency matrix
adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] =
adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] =
adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] =
adj[9][6] = adj[6][8] = adj[8][5] = true;
//path which needs to be checked
char path[] = "ABBECCD".toCharArray();
if (petersonGraph(path, path[0] - 'A') ||
petersonGraph(path, path[0] - 'A' + 5)) {
System.out.print(res);
} else {
System.out.print("-1");
}
}
}

Output

The path is: 0169723

Implementation in Python

adj = [[False for i in range(10)] for j in range(10)]
result = [0]
# we are applying breadth first search
def findthepath(S, v):
result[0] = v
for i in range(1, len(S)):
if (adj[v][ord(S[i]) - ord('A')] or
adj[ord(S[i]) - ord('A')][v]):
v = ord(S[i]) - ord('A')
else if (adj[v][ord(S[i]) - ord('A') + 5] or
adj[ord(S[i]) - ord('A') + 5][v]):
v = ord(S[i]) - ord('A') + 5
else:
return False
result.append(v)
return True
# adjacency matrix to make connections between the connected nodes
adj[0][1] = adj[1][2] = adj[2][3] = \
adj[3][4] = adj[4][0] = adj[0][5] = \
adj[1][6] = adj[2][7] = adj[3][8] = \
adj[4][9] = adj[5][7] = adj[7][9] = \
adj[9][6] = adj[6][8] = adj[8][5] = True
# path to be checked
S= "ABBECCD"
S=list(S)
print("The path is: ")
if (findthepath(S, ord(S[0]) - ord('A')) or
findthepath(S, ord(S[0]) - ord('A') + 5)):
print(*result, sep = "")
else:
print("-1")

Output

The path is: 0169723

Let us analyze the time and complexity of this approach.

Complexity analysis

Time complexity

This approach will take O(V+E) times where V is vertices and E is the number of edges.

Frequently Asked Questions

What are graphs?

A graph is a popular data structure made up of a limited number of nodes (also known as vertices) and a limited number of connected edges. An edge is a pair (x,y) that indicates that the x vertex is connected to the y vertex.

What is directed and undirected graphs?

Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.

What are cyclic and acyclic graphs?

If a network has a cycle—a continuous set of nodes without any repeating nodes or edges that connects back to itself—then it is said to be cyclic. Acyclic graphs are those without cycles.

Conclusion

In this blog, we discussed the Peterson graph problem. We understood this problem with the help of an example. Then we discussed its algorithm. After that, we discussed its implementations in other languages like C++ and java. In the end, we saw the complexity analysis of the approach.