D1, C2 - Graphs & Networks Flashcards
What are the points on graphs called
Vertices or Nodes
What are the lines on graphs called
Edges or Arcs
What is a graph that has number associated with an edge or arc called
Weighted graph or Network
What is a vertex set
A set of all the vertices
e.g. A, B, C, …
What is a edge set
A set of all the edges
e.g. AB, AC, BC, …
What is a subgraph
A part of a graph
What is the degree / valency / order of a vertex
The number of edges incident (coming out of the vertex)
What are the types of degree for a vertex (2)
Odd
Even
What is a walk
Any route through a graph from a vertex to a vertex
What is a path
A walk in which no vertex is visited more than once
What is a trail
A walk in which no edge is visited more than once
What is a cycle
A walk in which the start and end vertex are the same. No other vertex is visited more than once
What is a Hamiltonian cycle
A cycle that includes every vertex
What is a connected graph
A graph will all of its vertices connected
What is a loop
An edge that starts and finishes at the same vertex
What is a simple graph
A graph with no loops and at most one edge connecting any pair of vertices
What is a directed graph (digraph)
A graph where all the edges are directed, i.e. have direction arrows on them
What is an undirected graph
A graph where the sum of the degrees (of the vertices) is equal to 2 * number of edges
Number of odd vertices = even (or zero)
Euler’s Hand-shaking Lemma
A graph has 5 nodes and 8 edges. The valencies of the nodes are x, x-1, x+1, 2x-1, x-1. Find x
By Euler’s Hand-shaking Lemma
Total valency = 2 * number of edges
x + x-1 + x+1 + 2x-1 + x-1 = 2 * 8
6x - 2 = 16
x = 3
What is a tree
A connected graph with no cycles
What is a spanning tree
A subgraph that includes all the vertices of a graph and is also a tree
What is a complete graph
A graph where every vertex is connected to every other vertex
What are isometric graphs
Graphs which show the same information drawn differently
What must be the same with isometric graphs
Number of edges
Number of vertices
Same valencies