Other types of graphs.
How to contact me.
The basic definitions on the
graph theory main page introduce finite simple graphs. There are other definitions used by some researchers.
Obviously, if the vertex set or the edge set (or both) is infinite, we say the graph is infinite. I have not dealt with infinite graphs on this site. You will find that there is not always one obvious way to generalize a finite parameter in the infinite case.
A loop is an edge with both endpoints the same vertex. A multiple edge is non-empty collection of edges between one pair of vertices. A graph which is permitted to contain loops and multiple edges is called a general graph.
A directed edge (or arc) vw is an edge from v to w. One could think of a directed edge as an ordered pair, and an undirected edge as an unordered pair. A digon is a directed cycle of length two.
A hyperedge is an edge that meets an arbitrary number of vertices (think of a hyperedge as a subset of the vertex set).
A graph is directed if every edge is directed. If we replace each directed edge of a directed graph H with the corresponding undirected edge, the resulting graph is the underlying graph of G. An oriented graph M is a directed graph whose underlying graph is simple. That is M has no loops, no multiple edges, and no digons.
A hypergaph is a graph with hyperedges. (Some people just say edges instead of hyperedges.) Alternately, a hypergraph is a vertex set V together with a collection of subsets (the edges) of the vertex set. A hypergraph is k-uniform if every edge contains exactly k vertices. As with infinite graphs, the generalization of a parameter might not be obvious. For example, a proper m-colouring of a graph involves assigning coluurs to the vertices so that every edge has exactly two colours. For a hypergraph, we could ask that every hyperedge contains at least two colours, or that every hyperedge has all of its vertices of different colours.
Last modified September 1, 2000, by S.C. Locke.