graph definitions Flashcards
define graph:
vertices connected by edges
define network:
a weighted graph
define subgraph:
part of a graph
define degree:
number of vertices connected to a specified one
define valency:
number of vertices connected to a specified one
define order:
number of vertices connected to a specified one
define walk:
a route along the edges of a graph
define path:
a walk that repeats no vertices
define trail:
a walk that repeats no edges
define cycle:
a path that returns to the starting vertex
a hamiltonian cycle:
a cycle that includes every vertex
define simple graph:
a graph with no loops and with at most one edge connecting any pair of vertices
define digraph:
a directed graph
define euler’s handshaking lemma:
in an undirected graph, the sum of the degrees of the vertices = twice the number of edges, so the number of odd vertices must be even
define tree:
a connected graph with no cycles
define spanning tree:
a tree containing all the vertices
define complete graph:
a graph where every vertex is connected to every other vertex
define isomorphic graphs:
graphs that have the same edges and vertices that connect in the same way, but are drawn differently
define eulerian graph:
a graph that contains a trail that includes every vertex and edge and returns to the starting vertex (connected graphs with even vertices always are)
define semi-eulerian graph:
a graph that contains a trail that includes every vertex and edge and ends on a different vertex to the starting one (connected graphs with one pair of odd vertices always are)
