This is an old revision of the document!


Chapter 3

3.1 Basic Definitions and Applications

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?

3.2 Graph Connectivity and Graph Traversal

Already learned what it means to be connected - now looking at what we can do with that

Breadth First Search

  • Looks at one node then all the nodes attached to it then all the nodes attached to each of those new nodes, goes by layers
  • layer represents how far it is from root node, (also node in layer 5 is two away from node in layer three etc)
  • can find shortest path with BFS

Theorem 3.3

  • for each j >= 1, Lj produuced by BFS consists of all nodes at exactly j distance from s. There is a path from s to t if and only if tappears in some layer.
courses/cs211/winter2012/journals/carrie/ch3.1327894957.txt.gz · Last modified: 2012/01/30 03:42 by hopkinsc
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0