D1 Flashcards
What is a graph?
A set of vertices connected by arcs.
What is the weight of an arc?
The number/length associated with the arc.
What is the degree/valency of a vertex?
The number of arcs connected to it.
What is a path?
A sequence of arcs leading from one vertex to another in which no vertex is repeated.
What is a cycle?
A closed path between vertexes.
When is are two vertices connected?
If there is an arc between them.
When is a graph connected?
When all of the vertices are connected.
What is a directed edge?
An arc with a direction associated to it.
What is a tree?
A connected graph with no cycles.
What is a spanning tree?
A subgraph that includes all of the vertices of the graph and is also a tree.
What is a complete/connected graph?
A graph in which all of the vertices are connected to each other.
What is a bipartite graph?
A graph consisting of two sets of vertices, X & Y. Arcs can only join between the groups not within them.
What is a matching?
The pairing of some elements in a bipartite graph.
What is a complete matching?
When all of the elements are paired.
What is a subgraph?
A graph whose vertices belong to a larger graph.
