Foundations Of Computer Science – Graphs And Probability Revision

March 29, 2014 by in category Computer Science, Notes tagged as , , , , , , , , , with 0 and 0
Home > Blog > Computer Science > 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 k and C such that for x > k, f(x) leq C*g(x).

Summation

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

 

© Evan Smith 2009 - 2017