Graphs

Graphs are pervasive in computer science. Graphs can give a lot of information and be used to solve so many problems. Graphs can be defined by two sets, one with the vertices (the nodes in the graph) and one with the edges (how the nodes connect).

Introduction and Types

Graphs can have the following attributes:

• Undirected (there is not direction for the edges) or directed
• Simple (no edges connect the same two vertices) or multigraph
• Connected (you can traverse from any vertex to any other) or not-connected
• Cyclic or acyclic (has no cycles)
• Sparse (a lot of edges are missing, graph not connected that much) or dense

Emergent properties of graphs are:

• Loops: The edge connects the vertex to itself
• Cycles: Following one "path" of edges leads back to the same vertex

Vertices can also have the property of their degree (how many edges they have).

Representation

There are many ways to represent graphs.

Adjacency matrices are a way to do this, it requires (# of vertices)^2 amount of storage, but the lookup and edge time is O(1) it looks like:

Adjacency matrices are better when the matrix is dense

Adjacency lists is another way to do this, it requires much less storage, but it takes a larger lookup time.

Adjacency lists are better for sparse matrices.

Isomorphisms of graphs

#question why is flipping the little components and isomorphism

See Also

1. [[computer-science]]