Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM10 - Coggle Diagram
MM10
Graph
Collection of points in the place called "vertices" (V) some of them connected by line segments called "edges" (E)
-
Undirected Graphs
If (u, v) is equal to (v, u), the vertices are called adjacent and the edges undirected
If all edges in a graph are undirected, it is a undirected graph
Directed Graphs
If (u, v) and (v, u) are no the same, the edge is directed
-
-
Graph Representations
-
adjacency lists
collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list's vertex
Uses less space if the graph is sparse despite the extra storage consumed by pointers of the linked lists
-
Path
if all vertices of a path are distinct, the path is said to be simple
-
A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v
A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the same edge more than once. A graph without a cycle is called an acyclic graph
-
Topological Sorting
-
On each iteration, a vertex with no incoming edges is deleted from the digraph