• Unit 7: Graphs

    Graphs are formal mathematical representations of networks, collections of objects, events, or set elements that lead naturally from one to another. In this unit, we will examine the formality of graphs. Graphs are extremely useful in business, science, and engineering. In this unit, we will discuss how to understand graphs, how to build them, how to manipulate them, and how to use them.

    Completing this unit should take you approximately 9 hours.

    • Upon successful completion of this unit, you will be able to:

      • state the components of a graph;
      • describe the two principal graph traversal paradigms;
      • explain the difference between directed and undirected graph; and
      • use graphs to solve applications involving associated events.

    • 7.1: A Less-Formal Introduction

      • Basic Graph Theory Page

        We begin with a top-level view of graphs by looking at definitions, structure, and dynamics.

    • 7.2: A Formal Introduction

      • Introduction to Graphs Page

        Now that you have the general idea, we proceed with the formality required to gain an intuitive idea of what graphs are and what could potentially be done with them.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • 7.3: Graph Structures

      • Data Structures for Graphs Page

        Transitioning to practicality, we now learn about how data can be structured so that graphs are correctly formed for application.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • 7.4: Graph Node Connectivity

      • Connectivity Page

        Which nodes are connected, directly or indirectly? Between which nodes is there a path from one node to another? Those are the questions we deal with now. This is part of the topic of graph traversal, encountering a series of connected nodes in a graph or subgraph.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • 7.5: Graph Traversals

    • 7.6: Graph Optimization

      • Graph Optimization Page

        A common thread that connects all the topics in this unit is the opportunity to optimize (maximize or minimize) some quantity that is associated with a graph. For instance, we may decide to select a path from one node to another based on the weight of the connections between those nodes. The weights refer to some aspect of the situation at hand, like distance, cost, or importance.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • 7.7: Planarity and Colorings

      • Planarity and Colorings Page

        Annotating a graph so that it contains additional information is very important as the complexity of an application increases. Generally, the more complex the technology, the more precise needs to be its descriptive information.

      • Try It Now Book

        Work these exercises to see how well you understand this material.

    • Unit 7 Assessment

      • Unit 7 Assessment Quiz
        Receive a grade

        Take this assessment to see how well you understood this unit.

        • This assessment does not count towards your grade. It is just for practice!
        • You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
        • You can take this assessment as many times as you want, whenever you want.