Transcript Isomer 38:2

Problem of the Day:
Describe using set descriptor notation the
complements of
(a) { , a, aa, aaa} over ∑ = {a}
(b) { , a, aa, aaa} over ∑ = {a,b}
(c) {0,1}* {0010} {0,1}* over ∑={0,1}
(d) {001} {0,1}* over ∑={0,1}
(e) {0,1}* {1101} over ∑={0,1}
1
Announcements
Tutorial #2 has been added to connex (it was on
the class web pages before). You can attend
both sections if you need extra help.
Assignment #1 is due at the beginning of class
this Fri. Sept. 24. Hand it in on paper (not
electronically).
Make sure you sign the class attendance sheet
each class.
If you want more time for our proof of the day,
the notes are usually posted some time the night
before or come to class early.
2
Introduction to Graph Theory
Introduction to graph theory (review of
CSC 225). Many of the hard problems
(problems for which we do not have a
polynomial time algorithm) studied at
the end of the class are questions about
graphs.
3
An undirected graph G consists of a set V of vertices
and a set E of edges where each edge in E is associated
with an unordered pair of vertices from V.
The degree of a vertex v is the number of edges
incident to v.
If (u, v) is in E then u and v are adjacent.
A simple graph has no loops or multiple edges.
Exercise: prove by induction that a simple graph G on n
vertices has at most n(n-1)/2 edges.
4
Internet taken from:
http://www.netdimes.
org/asmap.png
5
Travelling Salesman
From:
Ehsan Moeinzadeh
Guildford, Surrey,
United Kingdom
6
Graphs representing chemical molecules
7
8
A cycle of a graph is an alternating sequence of
vertices and edges of the form v0, (v0, v1), v1,
(v1, v2), v2, (v2, v3), … ,vk-1, (vk-1, vk), vk where
except for v0 = vk the vertices are distinct.
Exercise: define path, define connected.
A tree is a connected graph with no cycles.
A subgraph H of a graph G is a graph with
V(H)  V(H) and E(H)  E(G).
H is spanning if V(H) = V(G).
Spanning tree- spanning subgraph which is a tree.
9
Strange Algorithms
Input: a graph G
Question: does G have a spanning tree?
This can be answered by computing a
determinant of a matrix and checking to see
if it is zero or not.
Don’t make assumptions about what my
algorithms for Hamilton Path/Hamilton cycle
are doing! Treat them as a black box.
10
Fullerenes
• Correspond to 3-regular planar graphs.
• All faces are size 5 or 6.
• Euler’s formula: exactly 12 pentagons.
11
Nobel Prize in Chemistry 1996
In 1996, the Nobel Prize in Chemistry was
awarded jointly to Robert Curl, Harold
Kroto and Richard Smalley for their
discovery of fullerenes.
Prof Robert F. Curl Jr
Photo: P. S. Howell
Prof Sir Harold W. Kroto
Prof Richard E. Smalley
Photo: Prudence Cummings Photo: P. S. Howell, Rice
Hamilton Cycles
A cycle which
includes all the
vertices of a
graph.
Conjecture: Every
fullerene has at
least one Hamilton
cycle.
13
Min Number of Hamilton Cycles
14
Conjecture
For all fullerenes except isomer 38:2, every
edge is in at least one Hamilton cycle
Isomer 38:2
15
Conjecture
For all isomers
except 38:2 and
40:8, no edge is in
every Hamilton
cycle.
e
Isomer 40:8
16
Incorrect Conjecture
Every fullerene has
some Hamilton cycle
with no 6-cycles like
this:
Isomer
74:5689
17
Regular
Languages
http://eloquentjavascript.net/img/xkcd_regular_expressions.png
18
Operations on Languages:
1. Complement of L defined over Σ =
= { w  Σ* : w is not in L }
2. Concatenation of Languages L1 ۰ L2 = L1 L2 =
{w= x۰y for some x  L1 and y L2}
3. Kleene star of L, L* = { w= w1 w2 w3 … wk for
some k ≥ 0 and w1, w2, w3, … ,wk are all in L}
4. L+ = L ۰L*
(Concatenate together one or more strings
from L.)
19
Σ* = set of all strings over alphabet Σ
Language over Σ – any subset of Σ*
Examples: Σ = {0, 1}
L1 = { w  Σ* : w has an even number of 0’s}
L2 = { w  Σ* : w is the binary representation of
a prime number with no leading zeroes}
L3 = Σ*
L4 = { } = Φ
L5 = { ε }
20
L2= {w  {0,1}* : w is the binary representation
of a prime with no leading zeroes}
The complement is:
{w  {0,1}* : w is the binary representation of a
number which is not prime which has no leading
0’s or w starts with 0}
Note: 1 is not prime or composite. The string 1 is
in the complement since it is not in L.
21
Matrix multiplication:
1
2
1
1
0
1
1
1
1
1
1
2
1
1
0
1
=
=
3
3
1
1
1
3
1
3
Concatenation:
ab ۰ bb = abbb
bb ۰ ab = bbab
22
Regular Languages over Alphabet Σ:
[Basis] 1. Φ and {σ} for each σ  Σ are
regular languages.
[Inductive step] If L1 and L2 are regular
languages, then so are:
2. L1 ۰ L2 ,
3. L1 ⋃ L2 , and
4. L1 *.
23
Regular expressions over Σ:
[Basis] 1. Φ and σ for each σ  Σ are
regular expressions.
[Inductive step] If α and β are regular
expressions, then so are:
2. ( αβ)
3. (α⋃β)
4. α*
and
Note: Regular expressions
are strings over
Σ ⋃ { (, ), Φ,⋃, * }
for some alphabet Σ.
24
Precedence of Operators
Exponents
Multiplication
Addition
highest
⇩
lowest
Kleene star
Concatenation
Union
25