Graphs

• Directed Graph

The ordered pairs in E represent the direction of the edge, i.e., (tail, head) tail is source vertex and head is the target vertex

Undirected Graph

The pairs in E are unordered pairs, i.e., there is no tail or head and there is no direction to the edge, e.g., (u, v) ∈ E is really the same edge as (v, u)

http://homepages.ius.edu/rwisman/C455/html/notes/AppendixB4/GraphBasics.htm

• Kinds of Graphs

Various flavors of graphs have the following specializations and particulars about how they are usually drawn.
Undirected Graphs.

In an undirected graph, the order of the vertices in the pairs in the Edge set doesn't matter. Thus, if we view the sample graph above we could have written the Edge set as {(4,6),(4,5),(3,4),(3,2),(2,5)),(1,2)),(1,5)}. Undirected graphs usually are drawn with straight lines between the vertices.
The adjacency relation is symetric in an undirected graph, so if u ~ v then it is also the case that v ~ u.

Directed Graphs.

In a directed graph the order of the vertices in the pairs in the edge set matters. Thus u is adjacent to v only if the pair (u,v) is in the Edge set. For directed graphs we usually use arrows for the arcs between vertices. An arrow from u to v is drawn only if (u,v) is in the Edge set. The directed graph below

http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html

• 4.1  Undirected Graphs

Graphs
A graph is a set of vertices and a collection of edges that each connect a pair of vertices


Glossary.
Here are some definitions that we use.

    A self-loop is an edge that connects a vertex to itself.
    Two edges are parallel if they connect the same pair of vertices.
    When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.
    The degree of a vertex is the number of edges incident on it.
    A subgraph is a subset of a graph's edges (and associated vertices) that constitutes a graph.
    A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices.
    A cycle is a path (with at least one edge) whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).
    The length of a path or a cycle is its number of edges.
    We say that one vertex is connected to another if there exists a path that contains both of them.
    A graph is connected if there is a path from every vertex to every other vertex.
    A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.
    An acyclic graph is a graph with no cycles.
    A tree is an acyclic connected graph.
    A forest is a disjoint set of trees.
    A spanning tree of a connected graph is a subgraph that contains all of that graph's vertices and is a single tree. A spanning forest of a graph is the union of the spanning trees of its connected components.
    A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.

http://algs4.cs.princeton.edu/41undirected/