click below
click below
Normal Size Small Size show me how
D1 Definitions
Graph Definitions
Question | Answer |
---|---|
Graph | a set of vertices (or nodes) together with a set of edges |
Edge | a line with a vertex at each end |
Loop | an edge with the same vertex at each end |
Degree (or Order) of a Vertex | the number of edges incident on it |
Simple Graph | a graph where there are no loops, and in which there is no more than one edge connecting any pair of vertices |
Walk | a sequence of edges in which the end of one edge (except the last) is the beginning of the next |
Trail | a walk where no edge is repeated |
Path | a trail where no vertex is repeated |
Cycle | a closed path |
Hamiltonian Cycle | a cycle which visits every vertex |
When is a graph connected? | if a path exists between every pair of vertices |
Tree | a simple connected graph with no cycles |
Digraph (directed graph) | a graph is which at least one edge has a direction associated with it |
Complete graph | a simple graph in which every pair of vertices is connected by an edge |
Incidence Matrix | a way of representing a graph by a matrix |
Isomorphic Graphs | Two graphs are isomorphic if one can be stretched, twisted or otherwise distorted into each other |
Planar Graph | a graph which can be drawn without any edges crossing |
Bipartite Graph | a graph in which the vertices fall into two sets and in which each edge has a vertex from one set at one end and from the other set at its other end |