Algorithms On Graphs: Difference between revisions
Jump to navigation
Jump to search
Adamcolton (talk | contribs) Created page with ";Graph: A graph is a set of vertices and a set of edges, each of which connects two vertices. ;Loop: An edge that connects a vertex to itself ;Simple Graph: A graph with no lo..." |
Adamcolton (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
== Week 1 == | |||
=== Graph Basics === | |||
;Graph: A graph is a set of vertices and a set of edges, each of which connects two vertices. | ;Graph: A graph is a set of vertices and a set of edges, each of which connects two vertices. | ||
;Loop: An edge that connects a vertex to itself | ;Loop: An edge that connects a vertex to itself | ||
;Simple Graph: A graph with no loops and no more than one connection between any set of vertices. | ;Simple Graph: A graph with no loops and no more than one connection between any set of vertices. | ||
=== Representing Graphs === | |||
We can store a graph as a list of edges. It can also be stored as a matrix. Or a list of lists, the top list being all the vertices and each sub list being the vertices it's connected to. | |||
;Density: Edges / vertices<sup>2</sup> | |||
[[Category:Notes]] | [[Category:Notes]] | ||
[[Category:Course Work]] | [[Category:Course Work]] | ||
Revision as of 02:48, 8 June 2016
Week 1
Graph Basics
- Graph
- A graph is a set of vertices and a set of edges, each of which connects two vertices.
- Loop
- An edge that connects a vertex to itself
- Simple Graph
- A graph with no loops and no more than one connection between any set of vertices.
Representing Graphs
We can store a graph as a list of edges. It can also be stored as a matrix. Or a list of lists, the top list being all the vertices and each sub list being the vertices it's connected to.
- Density
- Edges / vertices2