Chapter 2 Flashcards
Graph
Consists of vertices which are connected by arcs.
Weighted grpah
Numbers associated to each arc.
Subgraph
Part of the original graph.
Degree/valency/order
Number of edges incident to it
Walk
A route through a graph along edges fron one vertex to the next.
Path
A walk from in which no vertex is visited more than once.
Trail
A walk in which no edge is visited more than once.
Cycle
A walk in which the end vertex is the same as the start vetex and no other verted is visited more than once.
Hamiltonian cycle
Cycle that includes every vertrx.
Loop
Edge thag starts and finishes at the same vertex
Simple graph
A graph in which there are no loops and there is at most one edge connecting any pair of vertices.
Digraph
Directed graph/edges have a direction associated with them.
Euler’s handshaking lemma
Sum of the degrees of the vertices is equal to 2x(number of edges)
Tree
Connected graph with no cycles.
Spanning tree
Subgraph which includes all ther vertices of the original graph and is alo a tree
Complete graph
Graph which every vertex is directly connected by a single edge to each of the other vertices.
Isomorphic graph
Graphs which show the same information but may be drawn differently
Adjacency matrix
Describe the number of arcs joining the corresponding vertices.
Distance matrix
Entries represent the weight of each arc.
Planar graph
A graph that can be drawn in a plane such that no two edges meet except at a vertex.
