D1 Definitions Flashcards
What is a Graph?
A graph consists of vertices which can be connected by arcs / edges.
What is a Subgraph?
A graph of G, of whose vertices and edges belongs to G.
What is a Network?
A graph with a weight associated to each of its edges.
What is a Degree / Valency of a vertex?
The number of arcs connected to a vertex. A vertex is odd / even if it has odd / even degree.
Define a 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.
Define a Cycle / Circuit.
This is a closed path where the end vertex of the last arc is the start vertex of the first arc.
What makes vertices and graphs connected?
Two vertices are connected if there is a path between them.
A graph is connected if all of its vertices are connected.
What is a Tree?
A tree is a connected graph with no cycles.
What is a Spanning Tree?
A subgraph which includes all the vertices of G and is also a tree.
What is a Minimum Spanning Tree?
A spanning tree such that the total length of its arcs is as small as possible.
What is a Complete graph?
A graph in which each vertex is connected to every other vertex.
What is a Bipartite graph?
A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to those in Y (not vertices within a set).
Define a Matching.
The pairing of some or all of the vertices of one set X with the vertices of a second set Y.
Define a Complete Matching.
A matching in which every vertex of X is paired with a vertex of Y.
What is total float?
The total float F(i, j) of activity (i, j) is defined to be F(i, j) = lj – ei – duration (i, j), where ei is the earliest time for event i and l j is the latest time for event j.
