Difference between revisions of "Graph (graph theory)"
From Maths
m (Alec moved page Graph (discrete mathematics) to Graph (graph theory): Graph theory is a much better title, redirect can't hurt) |
m (Moving to a CS Definition rather than maths) |
||
| Line 16: | Line 16: | ||
==References== | ==References== | ||
<references/> | <references/> | ||
| − | {{Definition|Discrete Mathematics|Graph Theory}} | + | {{CS Definition|Discrete Mathematics|Graph Theory}} |
Latest revision as of 22:15, 13 January 2018
- 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!
Contents
| Graph | |
| (Discrete mathematics) | |
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:
Warning:That grade doesn't exist!
The message provided is:
Standard graph terminology
Warning:That grade doesn't exist!
Notes
- ↑ See Topology from Saul in 2015, I never found a source but he used trees!
References
- ↑ That formal languages hardback by my bed, sort it out later, DUBIOUS REFERENCE for graph, great for digraph
