Foundations Of Computer Science – Graphs And Probability Revision

Graphs

Simple Graphs

Are ordered pairs (V, E) where

  • V ∈ A set of all Vertices
  • E ∈ A set of all Edges

Multigraph

Are ordered pairs (V, E) where

  • V ∈ A set of all Vertices
  • E ∈ A bag of all Edges

[A bag is like a set but elements can be repeated]

Directed Graph

Arrows show direction on a directed graph.

Directed graphs are ordered pairs where

  • V ∈ A set of all Vertices
  • E ∈ A set of all Edges, where each Edge is an ordered pair of vertices.

Complete Graph

Every vertex is connected to every other vertex.

Connected Graphs

A graph is connected if every pair of vertices v,w can be connected by a path which starts at v and ends at w

A path in a graph is a sequence of oriented edges such that the end point of one oriented edge is the beginning of the next.

Circuits

A circuit is a path that starts and ends at the same point.

Euler Circuits

  • A Euler Circuit visits every edge exactly once.
  • All vertices have even degree.

Hamiltonian Circuits

  • A Hamiltonian Circuit visits every **vertex **exactly once.

Cycles

  1. Contain at least one edge.
  2. No edge is used twice
  3. No vertex (except the starting point) is visited twice.

Trees

A tree is a connected, undirected simple graph with no cycles.

Rooted Trees

Select one vertex and orient all edges to form a directed path from the root to all other vertices.

Leaf

A vertex with no children.

Internal Vertex

A vertex with children.

Ancestor

Vertices between the current vertex and the root.

Descendant

Vertices between the current vertex and the end of the tree.

Properties Of A Tree

  1. Between any pair of vertices, there is only one simple path.
  2. Adding a new edge to the tree creates a cycle.
  3. Removing an edges causes a disconnected graph.
  4. There is at least one leaf.
  5. If a tree has two or more vertices, there is at least one vertex with a degree equal to 1
  6. Any tree with n vertices has (n – 1) edges.

Prim’s Algorithm

(Minimal Spanning Tree)

  1. Start at a vertex
  2. Find all the edges connected to it
  3. Choose the cheapest edge
  4. Now choose the cheapest edge to a vertex we haven’t been to yet.
  5. Repeat until every vertex has been chosen.

Probability/Choosing

[  ^{n}P_{r} = frac{n!}{(n-r)!} hspace{10 mm} ^{n}C_{r} = frac{n!}{r!(n-r)!} ]

O( g(x) ) Definition (Big-Oh)

There exists two constants and such that for , .

Summation

[ sum_{i=1}^{n} i = 1 + 2 + 3 + … + n = { n(n+1) over 2 } ]

 

###