2. Graph Terminology #
Created Monday 30 March 2020
- Vertices - nodes are called vertices.
- Edges - a line that connects two vertices.
- Adjacent vertices - two vertices connected by a edge.
- Degree - this is defined for a vertex = number of edges connected to a vertex(incoming is taken as +ve for outgoing, if graph is directed)
- Path - An ordered set of edges from a vertex A to B.
- Connected graph - If every vertex is reachable from every other vertex, then this graph is called a connected graph. Simply said, there are no disjoint groups.
- Connected components - The groups of connected graphs in a given graph. For a connected graph, number of connected components is 1. For a non connected graph it is greater than one.
- Cycle - A path which starts from a vertex and comes back to the same vertex. A cycles must have at least 2 distinct edges in its path.
- Tree - a connected graph with no cycles.
Range of edges, vertices and degree. Given a graph V, E.
- minimum number of edges = 0. All vertices are seperate. A fully disconnected graph.
- minimum number of edges in a connected graph = all are connected but uses the least edges to connect = no cycles at all = A tree(except the root, number of edge vertex pairs are n-1) = n-1
- maximum edges = complete graph = each edge is connected to every other edge = all posssible connections among all vertices = ^n^C~2~ = n(n-1)/2