Decision: Graphs and Networks: Definitions Flashcards
Define a walk
A route through a graph along edges from one vertex to the next
Define a Path
A walk in which no vertex is visited more than once
Define a Trail
A walk in which no edge is visited more than once
Define a Cycle
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
Define a Hamiltonian Cycle
A cycle that includes every vertex
Define a Loop
An edge that starts and finishes at the same vertex
Define a Simple Graph
A graph in which there are no loops and there is at most one edge connecting any pair of vertices
Define a ‘2 vertices connected’
Two vertices are connected if there is a path between them.
Define a Directed Graph (Digraph)
A graph where the edges are directed
Define Euler’s handshaking Lemma
In any undirected graph, the sum of the degrees pf the vertices = 2* the number of edges. As a consequence the number of odd nodes must be even = Euler’s handshaking Lemma
Define a Tree
A connected graph with no cycles
Define a Spanning tree
A spanning tree of a graph is a subgraph which includes all the vertices of the original graph and is also a tree
Define a Complete graph
A graph in which every vertex is directly connected by a single edge to each of the other vertices
Define Isomorphic graphs
Graphs which show the same information but are drawn differently
Define a Adjacency matrix
A matrix in which every entry describes the number of arcs joining the corresponding vertices
