Chapter 2 Flashcards
A graph
Consists of vertices (nodes) which are connected by edges (arcs)
A subgraph
Is part of a graph
A weighted graph
Has a number associated with each edge (its weight)
The degree, valency or order of a vertex
Is the number of edges incident to it
A path
Is a finite sequence of edges, such that the end vertex of one edge of the sequence is the start vertex of the next, and in which no vertex appears more than once
A walk
Is a path in which you are permitted to return to vertices more than once
A cycle (circuit)
Is a closed path, so the end vertex of the last edge is the start vertex of the first edge
Two vertices are connected if
There is a path between them
A graph is connected if
All its vertices are connected
A loop
Is an edge that starts and finishes at the same vertex
A simple graph
Is one in which there are no loops and not more than one edge connecting a pair of vertices
Directed edges (in a digraph)
If the edges have a direction associated to them
A tree
A connected graph with no cycles
A spanning tree
Is a subgraph which includes all the vertices of the original graph and is also a tree
A bipartite graph
Consists of two sets of vertices, X and Y. The edges can only join vertices in X to vertices in Y, not vertices within a set
A complete graph
Is a graph in which every vertex is directly connected by an edge to each other vertices. If the graph has n vertices the connected graph is denoted kn
A complete bipartite graph
Is a graph in which there are r vertices in set X and s vertices in set Y (denoted k r,s)
Isomorphic graphs
Show the same information but are drawn differently
An adjacency matrix
Records the number of direct links between vertices
A distance matrix
Records the weights on the edges. Where here is no weight, this is indicated by ‘-‘
