Graph

G = (V, E), is a finite set of vertices, V, and a finite set of edges, E, where each edge (u, v) connects two vertices, u and v.

Adjacent Vertices

Two vertices, u and v, of a graph are _____ if there exists an edge (u, v).

Self-loop

an edge (u, u).

Multi-Graph

can have multiple edges between the same two vertices and self-loops

Simple Graph

graphs without self-loops and multiple edges between the same two vertices.

Incident Edge

If (u, v) is an edge in a graph G, (u, v) is ______ to vertices u and v.

Degree of a vertex

the number of edges incident on it (a vertex)

Isolated Vertex

A vertex whose degree is 0

Path of length k

from a vertex u to a vertex u' is a sequence (v0, v1, v2, ..., vk) of vertices such that u = vo, u' = vk and (vi-1,vi) is an edge in E for i = 1, 2, ... k. The length is the number of edges in the path.

Simple Path

A path is ______ if all vertices in the path are distinct

Sub-path

a contiguous subsequence of its vertices

Cycle

a path with k>0 where vo = vk and all the edges are distinct.

Simple cycle

A cycle is _______ if the vertices are distinct

Acyclic

A graph with no simple cycles

Connected Graph

every vertex is reachable from all other vertices.

Connected Components

the equivalence classes of vertices under the "is reachable from" relation

Eulerian Cycle

a circuit which uses every edge once

Eulerian Path

a path which uses every edge once.

Hamiltonian Cycle

a simple circuit that traverses all vertices

Hamiltonian Path

a simple path that traverses all vertices

Complete Graph

A _______ of n vertices, Kn, is a graph in which every pair of vertices is adjacent.

Bipartite Graph

A ____________ of n vertices is a graph in which the n vertices can be partitioned into two sets V1 and V2 such that for every edge (u, v), u is in one of the sets and v is in the other. Km,n is the Complete Bipartite graph where |V1|= m and |V2|= n.

Dirac's Theorem

If each vertex of a connected graph with n vertices is adjacent to at least n/2 vertices, then the graph has a Hamilton Circuit.

Incident to/from

In/out Degrees

Weakly Connected

A directed graph is ___________ if replacing all of its directed edges with undirected edges produces a connected (undirected) graph

Strongly Connected

A directed graph is _________ if every two vertices are reachable from each other.

Strongly Connected Components

the equivalence classes of vertices under the 'are mutually reachable' relation.

Isomorphic

Two graphs G = (V, E) and G' = (V', E') are _________ if there exists a bijection f: V -> V' such that (u,v) is in E iff (f(u), f(v)) is in E'

Tree

a connected undirected graph with no cycles.

Forest

a disconnected undirected graph with no cycles

Bridge

an edge which if removed would disconnect the graph.

Algorithm

a finite set of precise instructions which are performed to solve a problem

Running Time

Given n, the size of the input, we can express the ______ as a function of the input size, that is f(n).

Proposition

statement that is either true or false

Compound Propositions

modify, combine, and relate propositions to each other with words such as "or", "and", "not", and "if-then"

Negation of P

not P, is F when P is T and T when P is F

Conjunction of P and Q

P AND Q, only true when both are true

Disjunction of P and Q

P OR Q, true when one or both are true

Exclusive or

P XOR Q, only true when P is true or Q is true. false when both are false and when both are true

tautology

a compound proposition that is always true no matter what the truth values of the propositions that occur in it

contradiction

a compound proposition that is always false no matter what the truth values of the propositions that occur in it

contingency

a compound proposition that is neither a tautology nor a contradiction

implication, P-> Q

false when P is true and Q is false and true otherwise, P is called premise, antecedent or hypothesis and Q is called the conclusion or the consequence

Converse of P->Q

Q->P

Contrapositive of P->Q

NOT Q -> NOT P

Inverse of P->Q

NOT Q -> NOT P

Biconditional

P<->Q, is true when both P->Q is true and Q->P is true

Logically equivalent

If P<->Q is a tautology

Predicate

proposition whose truth depends on the value of one or more variables of a propositional function

universe of discourse

specifies the possible values of the variables in the predicate

quantifiers

symbols that are used to give more details about the predicate