Definitions For Graphs and networks Flashcards
Walk
A route through a graph along edges
Path
A walk where no vertex is visited more than once
Trail
A walk where no edge is visited more than once
Cycle
A walk in 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 including every vertex
An Eulerian cycle/circuit
A trail which traverses every arc and starts and finishes at the same vertex
Vertex set
List of vertexes
Edge set
List of edges
Degree or valency
Number of arcs/edges entering/incident to a vertex
A simple graph
No loops (line starting and finishing at the same vertex) and at most 1 line connecting vertices
Subgraph
A part of a graph
Connected graph
Where every vertex is connected to another
Digraph
A graph where edges have a direction specified
Weighted graph
A graph where edges have a number assigned to them
Tree
A tree is a connected graph with no cycles
spanning tree
A spanning tree of a graph G is a sub graph which includes all the vertices but only some edges in order for it to be a tree
A complete graph
Represented by Kn where n is number of vertices
A graph in which every vertex in connected by a single line to all other vertices
Isomorphic graphs
Graphs which show the same information but can be drawn differently
Adjacency matrix and graphs
Each entry in an adjacency matrix describes the number of arcs joining the corresponding vertices
Distance matrices and graphs
In a distance matrix the entries represent the weight of each arc not the number of arcs
Planar graph
A planar graph is one that can be drawn in a plane such that no two edges meet except at a vertex
