3.14 Graph theory: definitions and representation

3.14 Graph theory: definitions and representation Flashcards

IB Maths: Applications and Interpretation HL: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

14 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 14 cards
What is a graph in this topic?
A set of vertices joined by edges.
What does adjacent mean for two vertices?
They are joined by an edge.
Define the degree of a vertex.
The number of edges meeting at that vertex.
How is the sum of the degrees related to the number of edges?
The sum of the degrees is twice the number of edges.
What is a simple graph?
A graph with no loops and no more than one edge between any pair of vertices.
How many edges does a complete graph on nn vertices have?
n(n−1)2\frac{n(n-1)}{2}
What is a weighted graph?
A graph in which each edge carries a number, such as a distance, cost or time.
When is a graph connected?
When there is a path between every pair of vertices.
What is a subgraph?
A graph formed from some of the vertices and edges of another graph.
What is a tree?
A connected graph with no cycles.
How many edges does a tree on nn vertices have?
n−1n-1
In-degree and out-degree of a vertex in a directed graph?
In-degree: edges entering it. Out-degree: edges leaving it.
When is a directed graph strongly connected?
When you can get from any vertex to any other by following the directions of the edges.
What does a row sum of an undirected graph's adjacency matrix give?
The degree of that vertex.

Flashcards