A graph consists of the collection of vertices and edges, where an edge is a connection between any two vertices.
We can make a graph by drawing some lines connecting edges, which are joined by vertices.
Graph Theory Basics:
1. A directed graph which is generally denoted as G = (V, E) have a finite set V and a binary relation on V.
2. An undirected graph denoted as G = (V, E) has a finite set V and a set of multi-sets of two elements from V.
3. A graph is said to be complete if every pair of its distinct vertices is adjacent.
4. The precise way to represent a graph is to say that it is made up of the sets of vertices and the set of edges between these vertices.
5. A sub graph H of a graph G = (V, E) is a sub-graph if H = (V', E') satisfies V' is contained in V and E' is contained in E.
6. A simple path is a path with no vertex repeated.
7. If there exists a path from every vertex to every other vertex in the graph, then the graph is known as connected. A connected graph would remain the same, if taken by any vertex, if the vertices are physical and the edges as strings connecting them.
8. A cycle is a path, (a way from a vertex back to itself), which is a simple path, but here, the first and the last vertex are the same, that is the first vertex meets the last after completing its cycle.
9. A graph with no cycles is called a tree, and in a tree, there is only a single path between any two nodes. A tree on N vertices has exactly N - 1 edges.
10. A sub graph that has all the vertices and forms a tree is known as a spanning tree of a graph.
11. A group of disconnected trees is called a forest.
12. The graphs which have a direction associated with each edge are known as directed graphs.
13. An edge ab in a directed graph can be used in a path which goes from a to b only not from b to a.
|Calculator for Graphing||circle graph calculator|
|Ellipse Graphing Calculator||Equation Graphing Calculator|
|More topics in Graph Theory|
|Graph Coloring||Chromatic Number|