Graph Definitions Flashcards
What is a Graph?
Vertices connected by edges.
What is a subgraph?
A separate part of a graph
What is a weighted graph?
A graph with numbers associated with the edges
What does valency mean?
The number of edges incident to a vertex
What is a path?
The finite sequence of edges where no vertex appears more than once
What is a walk?
A path in which you are allowed to return to vertices more than once
What is a cycle?
A closed path where the first vertex is the last vertex
How are two vertices connected?
If there is a path between them
How is a path connected?
If all the vertices are connected
What is a loop?
An edge that starts and finishes at the same vertex.
What are the qualities of a simple graph?
It has no loops and no more than one edge connects a pair of vertices
What is a digraph?
A graph where the edges have directions associated with them
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A sub graph which is also a tree.
What is a bipartite graph?
Vertices in x only join to vertices in y. Not to vertices in the same set
What is a complete graph?
Every vertex is directly connected by an edge
What is a complete bipartite graph?
All vertices in x are directly connected to all vertices in set y
What is an Isomorphic graph?
The same as a bipartite graph but drawn differently
What is an adjacency matrix?
A record of the number of direct links between vertices
What is a distance matrix?
A record of the weight of the edges. No weight is record on the chart as (-)
