Graph (graph theory)

Not to be confused with: Digraph

Provisional page grade: B

This page is provisional

This page is provisional and the information it contains may change before this notice is removed (in a backwards incompatible way). This usually means the content is from one source and that source isn't the most formal, or there are many other forms floating around. It is on a to-do list for being expanded.The message provided is:

Unsure of whether or not 2 edges from the same node "to" the same node are allowed, and if so how they'd be distinct, eg 2 pipes of weight 5 are feasible between 2 nodes. Or even one node!

Graph

(Discrete mathematics)

A typical graph

Definition

Caveat:Here we describe a finite graph; infinite graphs are a thing, but they require special handling

A graph is defined to be an ordered pair $(V,E)$ where:

• $V$ be a finite set whose elements we shall call vertices (singular: vertex) or nodes (singular: node)
• $E$ is a finite set of edges (singular: edge), which may or may not have data associated with them:
  • No data: - An edge is defined as an (unordered) pair, $\{v_1,v_2\}$ of vertices $v_1,v_2\in V$, which need not be distinct (note that then $\{v,v\}$ is the singleton $\{v\}$, which represents an edge from $v$ to itself)
  • Data: - An edge is defined as the ordered pair, $(\{v_i,v_j\},d_{i,j})$ of an unordered pair $\{v_i,v_j\}$ specifying the edge as above and for some associated data, $d_{i,j}$

Warning:Multiple edges between the same vertices is not allowed in this model, yet having 2 edges 'from' a vertex 'to' itself both of weight 5 is allowed without problem in "real" graphs, indicating a limitation of our definition

Terminology

Grade: B

This page requires some work to be carried out

Some aspect of this page is incomplete and work is required to finish it
The message provided is:

Standard graph terminology

Warning:That grade doesn't exist!