Se le da una array n * n que representa un gráfico con n vértices, verifique si la array de entrada representa un gráfico de estrellas o no.
Ejemplo:
Input : Mat[][] = {{0, 1, 0},
{1, 0, 1},
{0, 1, 0}}
Output : Star graph
Input : Mat[][] = {{0, 1, 0},
{1, 1, 1},
{0, 1, 0}}
Output : Not a Star graph
Gráfico de estrella: El gráfico de estrella es un tipo especial de gráfico en el que n-1 vértices tienen grado 1 y un solo vértice tiene grado n – 1. Parece que n – 1 vértice está conectado a un solo vértice central. Un gráfico de estrella con un total de n – vértice se denomina Sn.
Aquí hay una ilustración para el gráfico de estrellas:
Enfoque: Simplemente recorra toda la array y registre el número de vértices que tienen grado 1 y grado n-1. Si el número de vértices de grado 1 es n-1 y el número de vértices de grado n-1 es 1, entonces nuestro gráfico debería ser un gráfico de estrella, de lo contrario no debería serlo.
Nota:
- Para S1, debe haber solo un vértice sin bordes.
- Para S2, debe haber dos vértices cada uno con grado uno o puede decir, ambos están conectados por un solo borde.
- Para Sn (n>2), simplemente verifique los criterios explicados anteriormente.
C++
// CPP to find whether given graph is star or not
#include<bits/stdc++.h>
using namespace std;
// define the size of incidence matrix
#define size 4
// function to find star graph
bool checkStar(int mat[][size])
{
// initialize number of vertex
// with deg 1 and n-1
int vertexD1 = 0, vertexDn_1 = 0;
// check for S1
if (size == 1)
return (mat[0][0] == 0);
// check for S2
if (size == 2)
return (mat[0][0] == 0 && mat[0][1] == 1 &&
mat[1][0] == 1 && mat[1][1] == 0 );
// check for Sn (n>2)
for (int i = 0; i < size; i++)
{
int degreeI = 0;
for (int j = 0; j < size; j++)
if (mat[i][j])
degreeI++;
if (degreeI == 1)
vertexD1++;
else if (degreeI == size-1)
vertexDn_1++;
}
return (vertexD1 == (size-1) &&
vertexDn_1 == 1);
}
// driver code
int main()
{
int mat[size][size] = { {0, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}};
checkStar(mat) ? cout << "Star Graph" :
cout << "Not a Star Graph";
return 0;
}
Java
// Java program to find whether
// given graph is star or not
import java.io.*;
class GFG
{
// define the size of
// incidence matrix
static int size = 4;
// function to find
// star graph
static boolean checkStar(int mat[][])
{
// initialize number of
// vertex with deg 1 and n-1
int vertexD1 = 0,
vertexDn_1 = 0;
// check for S1
if (size == 1)
return (mat[0][0] == 0);
// check for S2
if (size == 2)
return (mat[0][0] == 0 &&
mat[0][1] == 1 &&
mat[1][0] == 1 &&
mat[1][1] == 0);
// check for Sn (n>2)
for (int i = 0; i < size; i++)
{
int degreeI = 0;
for (int j = 0; j < size; j++)
if (mat[i][j] == 1)
degreeI++;
if (degreeI == 1)
vertexD1++;
else if (degreeI == size - 1)
vertexDn_1++;
}
return (vertexD1 == (size - 1) &&
vertexDn_1 == 1);
}
// Driver code
public static void main(String args[])
{
int mat[][] = {{0, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}};
if (checkStar(mat))
System.out.print("Star Graph");
else
System.out.print("Not a Star Graph");
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python to find whether
# given graph is star
# or not
# define the size
# of incidence matrix
size = 4
# def to
# find star graph
def checkStar(mat) :
global size
# initialize number of
# vertex with deg 1 and n-1
vertexD1 = 0
vertexDn_1 = 0
# check for S1
if (size == 1) :
return (mat[0][0] == 0)
# check for S2
if (size == 2) :
return (mat[0][0] == 0 and
mat[0][1] == 1 and
mat[1][0] == 1 and
mat[1][1] == 0)
# check for Sn (n>2)
for i in range(0, size) :
degreeI = 0
for j in range(0, size) :
if (mat[i][j]) :
degreeI = degreeI + 1
if (degreeI == 1) :
vertexD1 = vertexD1 + 1
elif (degreeI == size - 1):
vertexDn_1 = vertexDn_1 + 1
return (vertexD1 == (size - 1) and
vertexDn_1 == 1)
# Driver code
mat = [[0, 1, 1, 1],
[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]]
if(checkStar(mat)) :
print ("Star Graph")
else :
print ("Not a Star Graph")
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# to find whether given
// graph is star or not
using System;
class GFG
{
// define the size of
// incidence matrix
static int size = 4;
// function to find
// star graph
static bool checkStar(int [,]mat)
{
// initialize number of
// vertex with deg 1 and n-1
int vertexD1 = 0, vertexDn_1 = 0;
// check for S1
if (size == 1)
return (mat[0, 0] == 0);
// check for S2
if (size == 2)
return (mat[0, 0] == 0 &&
mat[0, 1] == 1 &&
mat[1, 0] == 1 &&
mat[1, 1] == 0);
// check for Sn (n>2)
for (int i = 0; i < size; i++)
{
int degreeI = 0;
for (int j = 0; j < size; j++)
if (mat[i, j] == 1)
degreeI++;
if (degreeI == 1)
vertexD1++;
else if (degreeI == size - 1)
vertexDn_1++;
}
return (vertexD1 == (size - 1) &&
vertexDn_1 == 1);
}
// Driver code
static void Main()
{
int [,]mat = new int[4, 4]{{0, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}};
if (checkStar(mat))
Console.Write("Star Graph");
else
Console.Write("Not a Star Graph");
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
PHP
<?php
// PHP to find whether
// given graph is star
// or not
// define the size
// of incidence matrix
$size = 4;
// function to
// find star graph
function checkStar($mat)
{
global $size;
// initialize number of
// vertex with deg 1 and n-1
$vertexD1 = 0;
$vertexDn_1 = 0;
// check for S1
if ($size == 1)
return ($mat[0][0] == 0);
// check for S2
if ($size == 2)
return ($mat[0][0] == 0 &&
$mat[0][1] == 1 &&
$mat[1][0] == 1 &&
$mat[1][1] == 0 );
// check for Sn (n>2)
for ($i = 0; $i < $size; $i++)
{
$degreeI = 0;
for ($j = 0; $j < $size; $j++)
if ($mat[$i][$j])
$degreeI++;
if ($degreeI == 1)
$vertexD1++;
else if ($degreeI == $size - 1)
$vertexDn_1++;
}
return ($vertexD1 == ($size - 1) &&
$vertexDn_1 == 1);
}
// Driver code
$mat = array(array(0, 1, 1, 1),
array(1, 0, 0, 0),
array(1, 0, 0, 0),
array(1, 0, 0, 0));
if(checkStar($mat))
echo ("Star Graph");
else
echo ("Not a Star Graph");
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript to find whether given
// graph is star or not
// define the size of incidence matrix
var size = 4;
// function to find star graph
function checkStar( mat)
{
// initialize number of vertex
// with deg 1 and n-1
var vertexD1 = 0, vertexDn_1 = 0;
// check for S1
if (size == 1)
return (mat[0][0] == 0);
// check for S2
if (size == 2)
return (mat[0][0] == 0 && mat[0][1] == 1 &&
mat[1][0] == 1 && mat[1][1] == 0 );
// check for Sn (n>2)
for (var i = 0; i < size; i++)
{
var degreeI = 0;
for (var j = 0; j < size; j++)
if (mat[i][j])
degreeI++;
if (degreeI == 1)
vertexD1++;
else if (degreeI == size-1)
vertexDn_1++;
}
return (vertexD1 == (size-1) &&
vertexDn_1 == 1);
}
// driver code
var mat = [ [0, 1, 1, 1],
[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]];
checkStar(mat) ? document.write( "Star Graph") :
document.write( "Not a Star Graph");
</script>
Producción:
Star Graph
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA