This is an old revision of the document!
Chapter 3
3.1
Definitions, definitions and more definitions all about graphs.
I know what a graph is, but just to review - edges E, and vertices (u,v) in V make up a graph. e connects from u to v.
A graph can be:
- Directed: go from vertx v to vertex u with edge e, but you cannot go from u to v on e
- Undirected: how we typically think of graphs the edge connects the two vertices with no direction.
- Tree: connected graph with no cycle
- Connected is when there are edges to all vertices. We use the edges to fine a path
- A certain type of path is a cycle that starts at one vertex and end up back at it by following edges
Different types of graphs:
- Transportation networks - algrotihm to find the best route might be an eventual problem, weight with milage, cost of fuel traffic etc.
- Communication networks - problem: find a place in the room to put your wireless router
- information networks: web etc.
- Social networks - still have bad memories from trying to create facebook in 111
- dependency networks
Theorems:
- every n-node tree has exactly n-1 edges: we will prove this in hw ps 3
- let G be an undirected graph of n nodes: Any two fo the following statements
- G is connected
- G does not contain a cycle
- G has n - 1 edges.
- There is a mistake in the above thm written on pg 78. (on instead of). also can't I just use this theorem to prove the one in our home work set?