Chapter 2 Key terms Flashcards
Graph
A graph consists of vertices (nodes) which are connected by edges (arcs)
Subgraph
A subgraph is part of a graph
Weighted Graph
If a graph has a number associated with each edge (its weight) then the graph is a weighted graph (network)
Degree or valency (or order)
(Of a vertex) is the number of edges incident to it
Path
A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
Walk
A walk is a path in which you are permitted to return to vertices more than once.
Cycle (circuit)
This is a closed ‘path’ i.e. the end vertex of the last edge is the start vertex of the first edge
Connected
Two vertices are connected if there is a path between them. A graph is connected is all its vertices are connected.
Loop
A loop is an edge that starts and finishes at the same vertex.
Simple Graph
This is one in which there are no loops and not more than one edge connecting any pair of vertices.
Directed edges and digraph
If the edges of a graph have a direction associated with them they are known as a directed edges and the graph is known as a digraph.
Tree
Is a connected graph with no cycles.
Spanning tree
A spanning tree of a graph, G, is a subgraph which includes all vertices of G and is also a tree.
Bipartite graph
Consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
Complete graph
Is a graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices the connected graph is denoted kn.
