Register

CMI2018-B-5

• recategorized by
439 views
1 votes
1 votes
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given  to you by a $0-1$ matrix $A$ of size $n\times n$  as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if $(i,j)$ is an edge in $G.$
A connected component in $G$ is a subgraph in which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
• recategorized by
User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
gatecse asked Sep 13, 2019
649 views
CMI2018-B-3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...
User Avatar
6 votes
6 votes
3 answers
3
gatecse asked Sep 13, 2019
786 views
CMI2018-A-4
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$ $2$ $-1$ $0$ $1$
Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$ For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ ...
User Avatar
1 votes
1 votes
2 answers
4
go_editor asked Dec 30, 2016
573 views
CMI2016-A-5
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices? $60$ edges and $20$ vertices $30$ edges and $20$ vertices $60$ edges and $50$ vertices $30$ edges and $50$ vertices
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?$60$ edges and $20$ vertices$30$ ed...
User Avatar
Link Copied!