Selected topics in finite mathematics/What is a graph
Appearance
A graph is a collection of vertices, some of which may be connected by edges. Typically a vertex is represented by a circle or point; an edge would be represented by a line connecting the vertices.
Objectives
[edit | edit source]The goal is to identify vertices and edges in a graph.
Details
[edit | edit source]A graph is made up of edges and vertices. A graph is said to be connected if for every pair of its vertices, there is at least one path connecting the two vertices.
Examples
[edit | edit source]- Consider figure E1, the graph with vertices "A", "B", "C", "D", and "E". There are six directed edges connecting these vertices. Each edge has an accompanying weight. A path of weight 51 is E-A-C-D. A cycle of weight 42 is B-A-C-B.
Nonexamples
[edit | edit source]- Consider figure E1. In this graph E-A-B is not a path, because A-B is not an edge.
FAQ
[edit | edit source]Q: What is a vertex?
A: Point
Q: What is an edge?
A: Lines connecting vertices, or points
Homework
[edit | edit source]- In figure H1, identify a vertex.
- In figure H1, identify an edge and its corresponding weight.
- In figure H1, find three different paths of total weight 8.
- In figure H1, find a cycle of weight 15.
- Redraw figure H1 so that vertex "H" is to the right of vertex "F"
- Remove vertex "B" from figure H1. (When removing a vertex, you need to remove all incident edges as well)
- Remove vertex "B" from figure H1, then find a cycle that uses all the remaining vertices.
Homework Solutions
[edit | edit source]- "A" is one of the vertices in figure H1. "B" is anther vertex, which is connected to all other vertices except "F".
- A-C is one of the edges in figure H1. Weight is 5.
- The paths C-A-B, E-C-F, and C-E-B-A each have a total weight of eight.
- The cycle G-B-H has a weight of 15.