Networks and graphs

Networks and graphs Flashcards

IB MYP Maths Extended: 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 are vertices and edges?
Vertices (nodes) are the points of a network. Edges (arcs) are the lines joining them.
What is the degree of a vertex?
The number of edges that meet at that vertex.
How is the sum of the degrees related to the number of edges?
The sum of the degrees equals twice the number of edges.
What is a path?
A route along edges that does not visit any vertex more than once.
What is a weighted network?
A network where each edge has a number, such as distance, time or cost.
How do you find the length of a path in a weighted network?
Add the weights of the edges it uses.
How do you find the shortest path?
Find the total weight of every possible path (or build up the shortest distances step by step) and choose the smallest.
What does an adjacency matrix show?
A 11 if two vertices are joined by an edge and a 00 if not.
What are the features of an adjacency matrix for an undirected network?
It is square and symmetric, with zeros on the diagonal; each row total is the degree.
What does an entry of M2\mathbf M^2 count?
The number of journeys with exactly two edges between those two vertices.
What is an Euler trail?
A route using every edge exactly once.
When does a connected network have an Euler circuit?
When every vertex has even degree.
When does a connected network have an Euler trail but not an Euler circuit?
When exactly two vertices have odd degree; the trail starts at one and ends at the other.
What is a Hamiltonian path?
A route that visits every vertex exactly once.

Flashcards