# Tag Info

2

The size of adjacency list representation is $\Theta(|E(G)| + |V(G)|)$, and not $\Theta(|E(G)|)$. For example, consider a graph with $n$ vertices and $0$ edges. The adjacency list corresponding to each vertex is empty. But storing the null pointer requires constant space for each vertex. Therefore, the size of the adjacency lists is $|V(G)|$ here.

2

The idea, in a nutshell, is that a graph does not contain an odd cycle iff it is 2-colorable (also known as bipartite). Your algorithm attempts to find a 2-coloring of the graph. In each connected component, the coloring is unique once we fix the color of one of the vertices, since all neighbors of a white vertex are black and vice versa. The algorithm uses ...

1

The shortest path between vertices $A$ and $Z$ (where $A\ne Z$) is the minimum over all edges $A\to B_i$ of the weight of that edge plus the shortest path from $B_i$ to $Z$. For general graphs, it isn't obvious how to optimize that, because some paths from $B_i$ to $Z$ may pass through $A$. In a dag, that can't happen, and so there is an easy algorithm: ...

1

In the figure, the bottom four vertices of the graph are red-colored vertices. $H$ has $5$ edges and $5$ vertices. $H'$ has $6$ edges and $4$ vertices.

Only top voted, non community-wiki answers of a minimum length are eligible