Jump to content

Selected topics in finite mathematics/What is a graph

From Wikiversity

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]
An example of a graph
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

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

Q: What is a vertex?

A: Point


Q: What is an edge?

A: Lines connecting vertices, or points

Homework

[edit | edit source]
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

[edit | edit source]
  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.