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 [ilmath](V,E)[/ilmath] where:

• [ilmath]V[/ilmath] be a finite set whose elements we shall call vertices (singular: vertex) or nodes (singular: node)
• [ilmath]E[/ilmath] 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, [ilmath]\{v_1,v_2\} [/ilmath] of vertices [ilmath]v_1,v_2\in V[/ilmath], which need not be distinct (note that then [ilmath]\{v,v\} [/ilmath] is the singleton [ilmath]\{v\} [/ilmath], which represents an edge from [ilmath]v[/ilmath] to itself)
  • Data: - An edge is defined as the ordered pair, [ilmath](\{v_i,v_j\},d_{i,j})[/ilmath] of an unordered pair [ilmath]\{v_i,v_j\} [/ilmath] specifying the edge as above and for some associated data, [ilmath]d_{i,j} [/ilmath]

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!