In this article, we will discuss about pendant vertices, non-pendant vertices, pendant edges, and non-pendant edges of the graph. We will first read the formal definition and then visualize it using the graph.
Degree Of the Vertex in a graph
The degree of the vertex in a graph is defined as the number of edges connected to the vertex.
In the given Graph,
Node 0 has 2 edges connected to it. Therefore it has degree 2.
Node 1 has 3 edges connected to it. Therefore it has degree 3.
Node 2 has 2 edges connected to it. Therefore it has degree 2.
Node 3 has 1 edge connected to it. Therefore it has degree 1.
Pendant Vertices
In a graph, pendant vertices are the vertices that have a degree of 1, meaning they are connected to only one edge. In trees, these pendant vertices are called terminal nodes, leaf nodes, or simply leaves because in the case of trees leaf node always has degree 1.
In the given graph, identify the pendant vertices:
Node 0 has one edge. Therefore it has degree 1.
Node 1 has 1 edge. Therefore it has degree 1.
Node 2 has 3 edges. Therefore it has degree 3.
Node 3 has two edges. Therefore it has degree 2.
Node 4 has two edges. Therefore it has degree 2.
Node 5 has one edge. Therefore it has degree 1.
So pendant vertices are nodes with degree 1.
These are Node 0, Node 1, and Node 5.
Implementation in C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all the pendant
// vertices
void printPendantVertices( map<int, vector<int>> G)
{
// iterating over all the edges for any node
// if the size of vector edge is 1, then it must be pendant vertex
for (auto it=G.begin();it!=G.end();it++) {
if (it->second.size() == 1) {
cout << "Node" << it->first << endl;
}
}
}
void insertIntoGraph(map<int,vector<int>>&G,int x,int y){
G[x].push_back(y);
G[y].push_back(x);
return;
}
// Driver Code
int main()
{
map<int, vector<int>> G;
int edges[5][2] = {{1,2}, {2,0}, {2,3}, {3,4}, {4,5}};
for(int i=0;i<5;i++){
insertIntoGraph(G, edges[i][0], edges[i][1]);
}
printPendantVertices(G);
return 0;
}
Output :
Node0
Node1
Node5
Non-Pendant Vertices
In a given graph, Let say G, Non-pendant vertices are those vertices that are non - pendant, i.e., the degree should be greater than 1. In the case of trees, non-pendant vertices are non-leaf nodes because it does not have degree 1.
In the given graph, identify the non-pendant vertices:
Node 0, has one edge. Therefore it has degree 1.
Node 1 has one edge. Therefore. Therefore it has degree 1.
Node 2 has three edges. Therefore it has degree 3.
Node 3 has two edges. Therefore it has degree 2.
Node 4 has two edges. Therefore it has degree 2.
Node 5 has one edge. Therefore it has degree 1.
So non-pendant vertices are nodes with degrees greater than 1.
These are Node 2, Node 3, and Node 4.
83+ registered 