Check for star graph | define the size of incidence matrix ; def to find star graph ; initialize number of vertex with deg 1 and n - 1 ; check for S1 ; check for S2 ; check for Sn ( n > 2 ) ; Driver code
size = 4 NEW_LINE def checkStar ( mat ) : NEW_LINE INDENT global size NEW_LINE vertexD1 = 0 NEW_LINE vertexDn_1 = 0 NEW_LINE if ( size == 1 ) : NEW_LINE INDENT return ( mat [ 0 ] [ 0 ] == 0 ) NEW_LINE DEDENT if ( size == 2 ) : NEW_LINE INDENT return ( mat [ 0 ] [ 0 ] == 0 and mat [ 0 ] [ 1 ] == 1 and mat [ 1 ] [ 0 ] == 1 and mat [ 1 ] [ 1 ] == 0 ) NEW_LINE DEDENT for i in range ( 0 , size ) : NEW_LINE INDENT degreeI = 0 NEW_LINE for j in range ( 0 , size ) : NEW_LINE INDENT if ( mat [ i ] [ j ] ) : NEW_LINE INDENT degreeI = degreeI + 1 NEW_LINE DEDENT DEDENT if ( degreeI == 1 ) : NEW_LINE INDENT vertexD1 = vertexD1 + 1 NEW_LINE DEDENT elif ( degreeI == size - 1 ) : NEW_LINE INDENT vertexDn_1 = vertexDn_1 + 1 NEW_LINE DEDENT DEDENT return ( vertexD1 == ( size - 1 ) and vertexDn_1 == 1 ) NEW_LINE DEDENT mat = [ [ 0 , 1 , 1 , 1 ] , [ 1 , 0 , 0 , 0 ] , [ 1 , 0 , 0 , 0 ] , [ 1 , 0 , 0 , 0 ] ] NEW_LINE if ( checkStar ( mat ) ) : NEW_LINE INDENT print ( " Star ▁ Graph " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ a ▁ Star ▁ Graph " ) NEW_LINE DEDENT