1. Apply Kruskal's algorithm to the graph in Figure 1. Highlight the steps
of the algorithm.
Figure 1
2. Consider the directed graph G = (V, E) in Figure 2.
Figure 2
(a) Determine the manifolds V and E.
b) What are the values of the node degrees (inner degree and outer degree) S, B, C, F.
c) For the graph G show a subgraph and, separately, a partial graph.
d) Identify a path and an elementary path in graph G (each having at least 5
nodes).
e) Identify a circuit and an elementary circuit in graph G (each with at least 4 nodes).
nodes).
(f) Walk the width of the graph G starting from node S, highlighting the tree
the resulting spanning tree.
2
(g) Go through the depth of the graph G starting from node S, highlighting the resulting
the resulting depth-visitation tree.
h) Represent the graph using the adjacency matrix.
i) Represent the graph using neighbour lists.
3. Consider a complete undirected graph G = (V, E) , |V|=n. What does the spanning tree look like
resulting from visiting the BFS? What about the DFS method?
4. Can there be a simple, cycle-free graph G = (V, E) such that VE ?
1 Laborator 8 1. Să se aplice algoritmul lui Kruskal pentru graful din figura 1. Să se pună în evidenţă paşii algoritmului. Figura 1 2. Se consideră graful orientat G = (V, E) din figura 2. Figura 2 a) Să se determine mulţimile V şi E. b) Care sunt valorile gradelor nodurilor (grad interior şi grad exterior) S, B, C, F. c) Pentru graful G să se prezinte un subgraf şi, separat, un graf parţial. d) Să se identifice un drum şi un drum elementar în graful G (fiecare având cel puţin 5 noduri). e) Să se identifice un circuit şi un circuit elementar în graful G (fiecare având cel puţin 4 noduri). f) Să se parcurgă în lăţime graful G pornind din nodul S, punându-se în evidenţă arborele de vizitare în lăţime rezultat. 2 g) Să se parcurgă în adâncime graful G pornind din nodul S, punându-se în evidenţă arborele de vizitare în adâncime rezultat. h) Să se reprezinte graful cu ajutorul matricei de adiacenţă. i) Să se reprezinte graful cu ajutorul listelor de vecini. 3. Se consideră un graf neorientat complet G = (V, E) , |V|=n. Cum arată arborele de acoperire rezultat în urma vizitării BFS? Dar pentru metoda DFS? 4. Poate să existe un graf simplu, fără cicluri G = (V, E) astfel încât VE ?