Studied by 5 people
Graph
A set of points that are connected by lines
Node
A vertex
Weighted graph
If there is a number associated with an edge
Valency
Order
Order
The number of arcs incident from a node
Walk
A route through the graph from one edge to the next
Path
Is a walk in which no vertex is visited more than once
Trail
Is a walk in which no edge is visited more than once
Cycle
Is a walk where the end vertex and start vertex are the same
Hamiliton Cycle
Is a cycle that includes every vertex
Loop
An edge that starts and finished at the same node
Simple Graph
Has no loops and each vertex is connected to another vertex only once
Connected graph
If all the vertices are connected
Digraph
A graph that has direction associated to it
Euler's handshaking lemma
In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges.
Tree
A connected graph with no cycles
Spanning Tree
a subgraph which includes all the vertices and is also a tree
Isomorphic
Two graphs showing the same information but drawn differently
completed graph
Is a graph where each vertex is connected to each of the other vertices by a single edge
Kn
A completed graph with n vertices
Degree
Order
Note
Flashcard