A simple graph is a set of nodes N and a set E of unordered pairs of distinct elements of N called edges.
![[Home]](wikipedia.png)
1 _____ 2 _____ 3
\ / /
\ / / an example of graph with five vertices and six edges
\ / /
5 _____ 4
Here, N = {1, 2, 3, 4, 5} and E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5)}.
Two nodes are considered adjacent if an edge exists between them. In the above graph, nodes 1 and 2 are adjecent, but nodes 2 and 4 are not.
The set of neighbors for a node contains each node adjacent to it. In the above graph, node 1 has two neighbors: node 2 and node 5.
A path is a series of nodes in that each node is adjacent to both the preceding and succeding node. A path is considered simple if none of the nodes in the path are repeated. In the above graph, {1, 2, 5, 1, 2, 3} is a path, and {5, 2, 1} is a simple path.
If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be connected.
A cycle is a path that begins and ends with the same node. In the above graph, {1, 5, 2, 1} is a cycle. A path is acyclic if it is not a cycle. A simple cycle is one in which the beginning node only appears once more, as the ending node.
A connected graph without cycles is said a tree; equivalently, a tree on n vertices is a connected graph with exactly n-1 edges. Trees are largely used as data structures in computer science (see tree data structure).
A complete graph is one in which every node is adjacent to every other node. The above graph is not complete. The complete graph on n vertices is often denoted by Kn. It has n(n-1)/2 edges (corresponding to all possible choices of pairs of vertices).
A planar graph is one which can be drawn in the plane without any two edges intersecting. The above graph is planar; the complete graph on n vertices, for n> 4, is not planar.
Graph Problems
lots more stuff here when I get time!