3.14 Graph theory: definitions and representation 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 vertices have?
- 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 vertices have?
- 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.