# 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