Decision - graph theory terms Flashcards
Vertex (verticies) / node
Points
Edges / arcs
Lines
Weighted graph
Numbers associated with an edge
Subgraph of graph G
Graph of G whose vertices belong to G and edges belong to G. A part of the original graph
Degree / valency / order
Number of edges connected to node
Walk
Route through the graph along the edges from one vertex to the next
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 where the end vertex is the same as the start vertex and no other vertex is visited more than once
Hamiltonian cycle
A cycle that includes every vertex
Connected graph
A graph where all vertices are connected (directly or indirectly)
Loop
Edge that starts and finishes at the same vertex
Simple graph
No loops and at most 1 edge connected any pair of vertices
Digraph (directed graph)
A graph where the edges have a direction associated with them
Euler’s handshaking lemma
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
Subgraph which includes all the vertices of the original graph and is also a tree
Complete graph
A graph in which every vertex is directly connected by a single edge to each of the other vertices
Isomorphic graphs
Graphs which show the same information but are drawn differently
Adjacency matrix
Describes the number of arcs joining the corresponding vertices
Distance matrix
Describes the weight of each arc not the number of arcs
Planar graph
A graph that can be drawn in a plane such that no two edges meet except at a vertex
Minimum spanning tree
A spanning tree where the total weight of the arcs is as small as possible
