decision Flashcards
Kruskals algorithm
List arks in ascending order of weight
add arks in ascending order of weight not making cycles
Prims algorithm
Choose any starting vertex
choose arc of least weight that joins to vertex already in the tree
route inspection algorithm
Shortest distance through all nodes
identify all odd vertices ucing valency table
consider all pairings choose pair with smallest sums to repeat
Eulerian graph or network
Is one which contains a trail that includes every edge and starts and finishes at the same vertex. This trail is called an Eulerian circuit.Any connected graph whos vertexes are all even is Eulerian
Semi-Eulerian graph or network
one which contains a trail that includes every edge but starts and finishes and different vertices.Any connected graph with exactly two odd verteces is semi-Eurelian
Weighted graph or network
If a graph as a number associated with each edge
subgraph
is a graph, each of whose vertices belong to the original graph and each of whose edges belongs to the original graph. It is part of the original graph
Degree,valency,order
The number of edges attached to a node
A walk
A Walk is a route through a graph along edges from one vertex to the next
A Path
A Path is a walk in which no vertex is visited more than once
A trail
A trail is a walk which no edge is visited more than once
A cycle
Is a walk which the end vertex is the same as the start vertex and no other vertex is visited more than once
A Hamiltonian cycle
A cycle that includes every vertex
connected graph
all the vertices are connected
A loop
A loop is an edge that starts and finishes at the same vertex
simple graph
A graph with no loops and at most one edge connecting a pair of vertices
directed graph (digraph)
if edges have a direction associated with them (directed edges)
sum of orders in an undirected graph =
2 x the number of edges, number of odd notes must then be even (eulers handshaking lemma )
tree
is a connected graph with no cycles
spanning tree of a graph
is a subgraph which includes all the vertices of the orignial graph and is also a tree
A complete graph
A graph in which every vertex is directly connected by a single edge to each other vertex
isomorphic graph
Graphs which show the same information but are drawn differently
