Flashcards
D1 glossary
Cards in this deck (15)
- 1Graphconsists of vertices or nodes, connected by edges or arcs
- 2Subgrapha graph within a graph
- 3Weighted graph or networka graph with a number (or weight) associated with each edge
- 4Degree or valencythe number of edges attached to a vertex
- 5Patha finite sequence of edges such that the end vertex of one edge is the start of the next and no vertex appears more than once
- 6Cycle or circuita closed path
- 7Digrapha graph made of directed edges
- 8Treeconnected graph with no cycles
- 9Spanning treea subgraph which includes all vertices of the main graph, and is a tree
- 10Minimum spanning treea spanning tree such that the total length of its arcs is as small as possible
- 11Complete grapha graph in which every vertex is connected to every other vertex
- 12Total float F(i,j) of an activity (i,j)latest time for event j - earliest time for event i - duration of arc
- 13Bipartite graphconsists of two sets of vertices, and arcs only between the two sets
- 14Matchingpairings between sets X and Y in a bipartite graph
- 15Complete matchinga matching where all vertices of set X are paired with a distinct vertice of set Y