Selected topics in finite mathematics/What is a graph

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

The goal is to identify vertices and edges in a graph.

Details

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

Figure E1: A graph with 5 vertices and 6 weighted edges.

1. 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

1. Consider figure E1. In this graph E-A-B is not a path, because A-B is not an edge.

FAQ

Q: What is a vertex?

A: Point

Q: What is an edge?

A: Lines connecting vertices, or points

Homework

Figure H1: A weighted graph

1. In figure H1, identify a vertex.
2. In figure H1, identify an edge and its corresponding weight.
3. In figure H1, find three different paths of total weight 8.
4. In figure H1, find a cycle of weight 15.
5. Redraw figure H1 so that vertex "H" is to the right of vertex "F"
6. Remove vertex "B" from figure H1. (When removing a vertex, you need to remove all incident edges as well)
7. Remove vertex "B" from figure H1, then find a cycle that uses all the remaining vertices.

Homework Solutions

1. "A" is one of the vertices in figure H1. "B" is anther vertex, which is connected to all other vertices except "F".
   
2. A-C is one of the edges in figure H1. Weight is 5.
   
3. The paths C-A-B, E-C-F, and C-E-B-A each have a total weight of eight.
4. The cycle G-B-H has a weight of 15.