Graphs

Question 1

Degree of Vertex

Answer 1

Number of Edges sticking out of undirected graph

Question 2

Self Loop

Answer 2

Edge starting and ending at same vertex

Question 3

Multigraph

Answer 3

If there are two edges between 2 vertices or there are self loops.

Question 4

Complete Graph

Answer 4

If there is an edge between every vertex of the graph

Question 5

Graph

Answer 5

Graph is represent using G=(V,E) where V is set of all vertices, and E is set of all edges

Question 6

Sum of degree of all vertices in undirected graph

Answer 6

Twice the number of edges 2|E|

Question 7

Eulerian Cycle

Answer 7

Cover every edge exactly once and come back to starting position

Question 8

Eulerian Path

Answer 8

Cover every edge exactly once but don’t come back to starting position

Question 9

Is every EC is EP?

Answer 9

Yes, but not vice-versa

Question 10

Connected Graph

Answer 10

If you can start from any vertex and reach any other vertex

Question 11

Connected Component

Answer 11

Is a piece of original graph within which you can start from any vertex and reach any other vertex. But you cannot grow the connected component by adding any more vertex.

Question 12

For Eulerian Cycle

Answer 12

Every timer we enter a vertex, we can exit it along some other edge. so the degree of vertex should be even. If the degree of any vertex is odd grapg can not have Eulerian cycle

Question 13

If the graph is connected and degree of every vertex is even does it have Eulerian Cycle

Answer 13

Yes

Question 14

If graph has 2 vertices with Odd Degree and rest with even degree

Answer 14

It has Eulerian Path

Question 15

Vertices with Odd dgree 0, EC or EP?

Answer 15

Eulerian Cycle

Question 16

Vertices with Odd degree 1, EC or EP?

Answer 16

none

Question 17

Vertices with Odd degree 2, EC or EP?

Answer 17

Eulerian Path

Question 18

Vertices with Odd degree 2,4,6 …. EC or EP?

Answer 18

Eulerian Path

Question 19

Graph Representation

Answer 19

1.Edge List: Simple but not efficient
2. Adjacency List:
3. Adjacency Matrix: n*n matrix
4. Adjacency Map:

Question 20

Number of edges at max in undirected graph

Answer 20

NC2 = n(n-1)/2 = O(n2) n => O(n square)

Question 21

Adjacency List

Answer 21

From the hashmap you get a vertex object and the class definition of vertex has an attribute which is a pointer to the adjacency list for the vertex. Vertex and adjacency list fused together called Object & Pointers approach.

This representation is not efficient if same set of vertices participate in different graph like road network, railway network or air route. Its better to save vertex separately
Facebook has millions of people and sparse graph of friendship b/w people.So better use Adjacency List.

Question 22

Adjacency Matrix

Answer 22

Symmetric Matrix: as its undirected graph. In directed graph it may not be symmetric.

Its good if we have to quickly tell if there is an edfe between u and v (u,v)

Diagonal is zero: No self loops

Question 23

Sparse Graph

Answer 23

In which |E|&laquo_space;|V|@

Question 24

Adjacency Map

Answer 24

Adjacency map uses a dictionary(hashmap key value pair) to store the neighbours of vertex v instead of list of neighbours( as in adjacency list)

Question 25

non connected graph

Answer 25

If graph is plit between multiple components, there can not be EC or EP even if the degree of every vertex is even !