7/25/22 Graph Theory

Class Notes

• A Graph is a diagram of relationships between properties with variables representing different values

  • It can be used to represent patterns/data

  • Examples of graphs:

    • Trees

    • Line plots

    • Axis

    • Circle graph

  • Vertices: dots on graphs

  • Edges: direct connection between 2 nodes

• Paths are lists of vertices, starting from vertex x → vertex y

  • Simple paths do not have duplicate vertices

  • Connected graphs have a possible path for any 2 vertices

• Cycle is a path but the 1st and last vertices are the same

  • A tree is a graph that does not have any possible cycles

• Directed paths do specify direction while undirected paths lack direction

• Adjacency matrices:

  • A matrix is similar to a table

    • It can be used to represent edges from points

    • The rows and columns are sorted in alphabetical order

  • Here’s a video on multiplying adjacency matrices: https://www.youtube.com/watch?v=3c2rzaO1h28&t=92s