Dm Test 3

Front 1

Language

Back 1

The set of all finite-length words using symbols from E will be denoted as E*. A language over E is a subset of E*

Front 2

Regular Grammar

Back 2

A regular grammar, G = (E, △, S, Π), consists of

An alphabet, E, also called the set of terminal symbols

A set, △, of nonterminal symbols.

A nonterminal symbol, S, called the start symbol

A set, Π, of replacement rules called productions

The productions are all in the form

N --> v

where N is a nonterminal and v ∈ (E U △)*. The string v satisfies the following conditions:

It must contain at most one nonterminal symbol

If v contains a nonterminal, it must be the rightmost symbol

If the only terminal symbol is λ, then there can be no nonterminal symbol

The string v must contain at least one terminal symbol

Front 3

Language Generated by a Grammar

Back 3

Let G = (E, △, S, Π) be a grammar. The language generated by G is the set of all words over E that can be derived from S. This set is denoted L(G). Thus,

L(G) = {w ∈ E* | S *=> w}

If the grammar, G, is a regular grammar, then L(G) is called a regular language.

Front 4

Simple Graph

Back 4

A simple graph, G = (V, E, φ), consists of a nonempty, finite set of vertices, V, a finite set of edges, E, and a one-to-one incidence function, φ, that maps edges to unordered pairs of distinct vertices.

Front 5

Graph

Back 5

A graph, G = (V, E, φ), consists of a nonempty, finite set of vertices, V, a finite set of edges, E, and an incidence function, φ, that maps edges to unordered pairs of vertices. If the two vertices in the unordered pair are the same vertex, the edge is called a loop.

Front 6

Handshake Theorem

Back 6

Let g = (V, E, φ) be a graph with ε = |E| edges. Then

E deg(v) = 2ε

v∈V

Front 7

PROOF Handshake Theorem

Back 7

For any vertex v, deg(v) is the number of edges incident with v. Every edge is incident with two vertices, so every edge is counted twice in the sum E deg(v).

Front 8

Complement of a Simple Graph

Back 8

Let G = (V, E, φ) be a simple graph. The complement of G is the simple graph (comp)G = (V, (comp)E, (comp)φ) where (comp)E contains an edge (comp)e with (comp)φ((comp)e) = vw if and only if E does not contain an edge e with φ(e) = vw.

Front 9

Bipartite Graph

Back 9

A graph G = (V, E, φ) is bipartite if E != 0 and if V can be partitioned into two disjoint subsets Va and Vb(B) such that for every edge e ∈ E, φ(e) = v1v2, where v1 ∈ Va and v2 ∈ Vb(B)

Front 10

Walk

Back 10

Of length k is a nonempty sequence of alternating vertices and edges, v0e1v1e2v2...ekvk, such that φ(ei) = v(i-1)vi, for i = 1, 2, ..., k. The vertices v0 and vk, are called the endpoints of the walk

Front 11

Trail

Back 11

Walk with no repeated edges

Front 12

Path

Back 12

Walk with no repeated vertices

Front 13

Closed

Back 13

Has length of at least one and its endpoints are the same vertex

Front 14

Circuit

Back 14

Closed trail

Front 15

Cycle

Back 15

Circuit in which endpoints are the only repeated vertices

Front 16

Unique Notation

Back 16

Do not have to use edges, v1v2v3 etc since it can be uniquely determined

Front 17

Adjacency Matrix of a Simple Graph

Back 17

Let G = (V, E, φ) be a simple graph with V = {v1, v2, ..., vn}. The adjacency matrix, A = (aij), is the n by n matrix whose rows and columns are indexed by the elements of V (in the same order). The element aij is defined by

1 if vi and vj are adjacent

aij = 0 otherwise

Front 18

Euler Trail; Euler Circuit

Back 18

Let G = (V, E, φ) be a graph without loops. An Euler trail in G is a walk that contains every edge in E exactly once. An Euler circuit in G is a circuit in which every edge appears exactly one time. (is a circuit if no vertices with odd degree)

Front 19

Hamilton Path; Hamilton Cycle

Back 19

Let G = (V, E, φ) be a multigraph. A Hamilton path in G is a walk that contains every vertex in V exactly once. A Hamilton cycle in G is a cycle that contains every vertex. (n >= 3 vertices, 8= min deg(v). If 8 <= (n/2), then G has a cycle)

Front 20

Isomorphic

Back 20

The graphs G = (V, E, φ) and G' = (V', E', φ') are isomorphic if there exists a one to one and onto function, zeta, from V to V' such that vi and vj are adjacent in G if and only if zeta(vi) and zeta(vj) are adjacent in G'.

In a multigraph, the adjacency condition needs to be enhanced by also requiring a one to one and onto function, double zeta, between the edge sets such that φ(e) = vivj if and only if φ'(double zeta(e)) = zeta(vi)zeta(vj)

Front 21

Regular Polyhedron

Back 21

A polyhedron is regular if

Every vertex has the same degree

The faces are all congruent

Front 22

Kuratowski's Theorem

Back 22

A graph, G, is nonplanar if and only if it contains a subgraph that is homeomorphic to either K5, or K3, 3

Front 23

Euler's Formula

Back 23

Let G be a connected, planar graph with e edges and n vertices. Let p be the number of regions in a planar embedding of G (including the region on the outside). Then

p = e - n + 2

Front 24

Five Regular Polyhedra

Back 24

Tetrahedron Equilateral triangles 4 4 6

Cube Squares 6 8 12

Octahedron Equilateral triangles 8 6 12

Dodecahedron Equilateral pentagons 12 20 30

Icosahedron Equilateral triangles 20 12 30

Front 25

Tree

Back 25

A connected graph with no cycles is called a tree

Front 26

Level

Back 26

The level of a node in a rooted tree is the length of the unique path from the root to that node. An alternate name for this number is the depth of the node. The root node is at level 0.

Front 27

Height; Balanced Trees

Back 27

The height of a rooted tree is the length of the longest path from the root to a leaf node. A tree of height h is balanced if all leaves appear at levels h - 1 and h.

Front 28

m-ary tree

Back 28

n >= 2 children at most

Front 29

Full m-ary tree

Back 29

Every interior node has exactly m children

Front 30

Complete m-ary tree

Back 30

Balanced tree having all levels filled except level h

Front 31

Maximal Complete Tree

Back 31

Complete and Full tree for which leaves appear in the final level

Front 32

PROOF The Number of Edges

Back 32

A tree with n nodes has n - 1 edges

Observe that every node except the root has exactly one adjacent edge on the unique path joining the node to the root. Every edge has two incident nodes. Partner each edge with its incident node that is farther from the root (determined by the respective levels). There is then a one to one pairing between edges in the tree and nonroot nodes. Since there are n - 1 nodes that are not the root, there must be n - 1 edges