Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
29 Cards in this Set
- Front
- Back
|
What is a graph? |
A graph consists of points (vertices or nodes) which are connected by lines (arcs or edges) |
|
|
What is a subgraph? |
Is a graph, each of whose vertices belongs to belong to the graph and each of whose edges belongs to this graph |
|
|
What is a weighted graph? |
If a graph has a number associated with each edge (usually called its weight) |
|
|
What is the degree/valency? |
The degree/valency 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 cycle/circuit? |
A closed path- the end vertex of the last edge is the start vertex of the first edge |
|
|
Why is Hamiltonian cycle? |
A cycle that passes through every vertex of a graph |
|
|
What is a digraph? |
If the edges of a graph have a direction associated with them |
|
|
What is a tree? |
A connected graph with no cycles |
|
|
What is a spanning tree? |
A subgraph of the graph which includes all the vertices of this graph and is also a tree |
|
|
What is a minimum spanning tree? |
Is a spanning tree such that the total length of its edges is as small as possible |
|
|
What is a dummy activity? |
Sometimes needed to correctly represent precedents (pretend line) |
|
|
What is the early event time? |
The earlier time each activity can start |
|
|
What is late event time? |
The latest time each activity can start without delaying the project |
|
|
What are critical activities? |
The activities that must be done at specific times |
|
|
What is a float? |
How much flexibility the other, non critical activities have |
|
|
What is a matching?
|
A one to one pairing of some or all of the elements of one set with the elements of a second |
|
|
What is a maximal matching?
|
A matching I which the number of arcs is as big as possible |
|
|
What is a complete matching?
|
|
|
|
What is a bipartite graph? |
Two sets of vertices X and Y. The edges only join vertices in X to vertices in Y not in the same set |
|
|
What is an isomorphic graph? |
Graphs that show the same information but are drawn differently |
|
|
What is a walk? |
A part where you can return to vertices more than once |
|
|
What is a loop? |
Starts and finishes at the same vertices |
|
|
What is an adjacency matrix? |
Records the number of direct links between vertices |
|
|
What is a distance matrix? |
Records the weights in the edges |
|
|
What is an Eulerian graph? |
A graph in which all Valencies are even |
|
|
What is a traversable graph? |
When it is possible to travel around every arc just once without lifting your own from the paper |
|
|
What is valency/ degree? |
The amount of arcs that are connected to one node |
|
|
What is a connected graph? |
When there is a path between every node |
