Networks and graphs 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 if two vertices are joined by an edge and a 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 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.