Fandom

Math Wiki

Graph (graph theory)

1,014pages on
this wiki
Add New Page
Talk0 Share

A graph G = (V,E) is an ordered pair of a set of its vertices and a multiset of its edges. The graph is the basic unit of graph theory.

Properties

order of a graph
The order of a graph G is |V|, the number of vertices in the graph.
size of a graph
The size of a graph G is |E|, the number of edges in the graph.
degree of a vertex
The degree of a vertex is the number of edges that connect to it. A loop is counted twice.

Types of graphs

Direction

Undirected graph
An undirected graph or simple graph is a type of graph where each edge is a 2-multiset of two vertices, thus order is not important.
Directed graph
A directed graph or digraph is a type of graph where E is a set and each edge is an ordered pair of two vertices, thus order is considered.
Mixed graph
A mixed graph is a type of graph that may contain both undirected and directed edges.

Connections

Multigraph
A multigraph is describe as a graph that allows multiple edges, that is, E may not be a set.
Simple graph
A simple graph is an undirected graph with no multiple edges (distinct elements in E) and no loops.

Other

Weighted graph
A weighted graph is a type of graph where each edge is assigned a number or weight. This is especially useful in problem-solving situations because it may represent things such as costs, flow, distances, lengths, and others.

There are some types of graphs which have edges with only one end (half-edge) and even no ends (loose edge).

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.