+
Graphs, Connectedness, And Trees

Graphs, Connectedness, And Trees

Rating:
Rating
(0)
Author: c o
Description:

To explore the concept of connectedness in graphs
To introduce the learner to spanning trees
To investigate the conditions underwhich a graph can be known to be connected

In this packet, we learn about connectedness and spanning trees in graphs.

(more)
See More

Try Our College Algebra Course. For FREE.

Sophia’s self-paced online courses are a great way to save time and money as you earn credits eligible for transfer to over 2,000 colleges and universities.*

Begin Free Trial
No credit card required

25 Sophia partners guarantee credit transfer.

221 Institutions have accepted or given pre-approval for credit transfer.

* The American Council on Education's College Credit Recommendation Service (ACE Credit®) has evaluated and recommended college credit for 20 of Sophia’s online courses. More than 2,000 colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.

Tutorial

Introduction

This packet continues where this introduction to graph theory left off.  If you have no previous experience with graph theory, you ought to go over the previous lesson.

Just in case you need a little refresher, the following list gives brief definitions of some of the terms used in this packet:

  • path: a set collection of edges leading from one vertex to another
  • cycle: a path that leads back to its starting point never having crossed the same edge twice
  • connected: a graph is connected when there is a path between any two vertices; if there exist two vertices for which no path can be formed between, the the graph is not connected.
  • tree: a connected graph with no cycles
  • adjacent: two vertices are called adjacent when they share an edge
  • degree: the degree of a vertex is the number of edges with which it is incident

Trees And Connected Graphs

IN this video, we work our way up to showing that every connected graph contains a spanning subtree.

Exploring Connectedness

In this video, we look at a criterion which is sufficient (but not necessary) to show that a graph is connected.