click below
click below
Normal Size Small Size show me how
D1 Graphs & Networks
Definitions
Term | Definition |
---|---|
Graph | Vertices (nodes) which are connected by edges (arcs) |
Subgraph | Part of a graph |
Degree / Valency | Number of edges incident to a vertex |
Path | A finite sequence of edges, in which no vertex appears more than once |
Walk | Like a path, but you can return to vertices |
Cycle | A closed path |
Loop | Starts a finishes at the same node |
Simple graph | A graph with no loops and not more than one edge connecting any pair of vertices |
Digraph | Graph with directed edges |
Tree | A connected graph with no cycles |
Spanning Tree | Subgraph including every vertex |
Bipartite graph | Two sets of vertices with edges joining between the sets |
Complete graph | Every vertex connected to every other vertex |
Isomorphic graphs | Different graphs showing the same information |
Eulerian graph | Connected graph with no odd nodes |
Semi-Eulerian graph | Connected graph with just one pair of odd vertices |