Further Maths - Graphs
See Also
- [[Further Maths - Eulerian Trails]]A
- [[Further Maths - Hamiltonian Cycles]]A
- [[Further Maths - Kruskals Algorithm]]?
Flashcards
What is a graph with weighted edges called?
A network.
What is the degree of a vertex?
The number of edges connected to it.
What is the order of a vertex?
The number of edges connected to it.
What is the valency of a vertex?
The number of edges connected to it.
What is the sum of degrees of all vertices in a graph?
Double the number of edges.
What is the property called when two graphs have the same vertices and edges?
They are isomorphic.
What is true about all these graphs?
What is true about all these graphs?They are isomorphic.
How can you show two graphs are isomorphic?
Match up vertex degrees and the edge set.
What is a walk in relation to graphs?
A sequence of edges where the end vertex of one edge is the start vertex of the next.
What is a trail in relation to graphs?
A walk where none of the edges are repeated.
What is a path in relation to graphs?
A trail where none of the vertices are repeated.
What is a cycle or circuit in relation to graphs?
A path that joins back up to the beginning.
What is a simple graph?
One with no loops and no double-edges.
Why is this graph not simple?
Why is this graph not simple?Because it has a loop.
What does it mean for two vertices to be connected?
There is a path between them.
What does it mean for a graph to be connected?
All pairs of vertices are connected.
What is a tree?
A connected graph with no cycles.
What is a complete graph?
One in which every possible pair of vertices is connected by an edge.
What is the notation for the complete graph with $n$ vertices?
What is the formula for the number of edges for $K _ n$ (the complete graph with $n$ verticies)?
What is a planar graph?
A graph that can be drawn so that none of the arcs cross.
2021-10-22
What is the order of the 4 ways you can get around a graph, going from least restrictive to most restrictive?
- Walk
- Trail
- Path
- Cycle
2021-11-04
What two things do you need to define a graph?
- Vertex set
- Edge set
2021-11-07
What degree does a loop contribute to a vertex?
What is a bipartite graph?
Graphs that consist of two or more independent sets of verticies that have no connections between themselves.
What is this an example of?
What is this an example of?A bigraph.
2022-05-16
How can you remember that a trail is where no edge is visited more than once?
It’s an “Eulerian trail”, not “Eulerian path”.
What are paths, trails and cycles all subsets of?
Walks.
What is a path?
A walk in which no vertex is visited more than once.
What is a cycle?
A walk in which the start and ends are the same.