1.
Introduction
2.
Sample Example
3.
Algorithm
4.
Implementation in C++
5.
Implementation in Java
6.
Implementation in Python
6.1.
Complexity analysis
7.
7.1.
What are graphs?
7.2.
What is directed and undirected graphs?
7.3.
What are cyclic and acyclic graphs?
8.
Conclusion
Last Updated: Mar 27, 2024

# Peterson Graph Problem

Shivani Singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

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
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
'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() {
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 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
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) {

//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)):
v = ord(S[i]) - ord('A')
else if (adj[v][ord(S[i]) - ord('A') + 5] or
v = ord(S[i]) - ord('A') + 5
else:
return False
result.append(v)
return True
# adjacency matrix to make connections between the connected nodes
# 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.

### 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.

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself.

Recommended Problems:

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass