D1 definition Flashcards
A graph
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).
A subgraph
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
A weighted graph or network
Has a number associated with each edge
The degree or valency of a vertex
Is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degree.
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 then once.
A cycle (circuit)
A cycle (circuit) is a closed path. ie the end vertex ofthe last edge is the start vertex of the first edge.
Two vertices are connected if…..
Two vertices are connected if there is a path between them.
A graph is connected if……
A graph is connected if all its vertices are connected.
Digraph
If the edges of a graph have a direction associated with them they are known as directed edges.
A tree is ….
A tree is a connected graph with no cycles.
What is a spanning tree…
A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also a tree.
Minimum spanning tree
A minimum spanning tree (MST) is a spanning tree such that the total length of its arcs is as small as possible.
completed graph
A graph in which each of the vertices is connected to every other vertex.
A bipartite graph
A bipartite graph consists of two sets of vertices X and L The edges only join vertices in X to vertices in { not vertices within a set.
A matching ….
A complete matching ….
A matching is the pairing of some or all of the elements of one set, X, with elements of a second set, L If every member ofXis paired with a member of )’the matching is said to be a complete matching.
