Graph (graph theory)

From Maths
Jump to: navigation, search
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[Note 1]

A graph is defined to be an ordered pair [ilmath](V,E)[/ilmath][1] 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!

Notes

  1. See Topology from Saul in 2015, I never found a source but he used trees!

References

  1. That formal languages hardback by my bed, sort it out later, DUBIOUS REFERENCE for graph, great for digraph