D1 - Graphs And Networks Flashcards
What is a sub graph?
Part of a graph.
What does a graph consist of?
Consists of vertices/nodes which are connected by edges/arcs.
What is a weighted graph?
If a graph has a number associated with each edge (weight) then the graph is weighted.
What is the degree of a vertex.
The degree or valency or order of a vertex is the number of edges incident to it.
What is a path?
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.
What is a walk?
A path in which you are permitted to return to vertices more than once.
What is a cycle?
A closed path, the vertex of the last edge is the start vertex of the first edge.
How are two vertices connected?
If there is a path between them.
How is a graph connected?
If all it’s vertices are connected.
What is a loop?
An edge that starts and finishes at the same vertex.
What is a simple graph?
One in which there are no loops and not more than one edge connecting any pair of vertices.
What is a digraph?
If the edges of a graph have a direction associate with them they are known as a directed edges and the graph is a digraph.
What is a tree?
A connected graph with no cycles.
What is a spanning tree of a graph?
A sub graph which includes all the vertices and is also a tree.
What is a bipartite graph?
Consists of two sets of vertices, X and Y, the edges only join vertices in X to vertices in Y, not within a set.
