PPT-graph-Graphs-theory-notes-introduction

graph

1. Graphs –Basic Concepts
William T. Trotter and Mitchel T. Keller
Math 3012 Applied Combinatorics
Spring 2009

2. What is a Graph?

3. What is a Graph?
A graphG is a pair (V, E) where V is a set (almost
always finite in this course) and E is a collection of 2-
element subsets of V.
Elements of V are called verticesand V is the vertex
set.
Elements of E are called edgesand E is the edgeset

4. Notation and Terminology
Usually, we write xyis an edge in G, or xyE rather
than {x,y} E.
Of course, xyis an edge if and only if yxis an edge.
When xyis an edge, we say xand yare adjacent.
When xand yare distinct and xyis not an edge, we
say that xand yare non-adjacent.

5. Data Files for Graphs
graph_data.txt
6
32
16
56
21
13
6 2

6. Subgraphs –Two kinds
H is a subgraphof G when every vertex of H is a
vertex in G, and every edge in H is an edge in G.
NO YES

7. Induced Subgraphs
H is an induced subgraphof G when every vertex of H
is a vertex in G, and every edge in G with both
endpoints in H is an edge in H.
NO YES

8. Isomorphic Graphs
G and H are isomorphicwhen there is a bijection
f : V(G) V(H) between their vertex sets so that
xand yare adjacent in G if and only if f(x) and
f(y) are adjacent in H.

9. Paths in Graphs
A pathin a graph (from xto y) is a sequence
x
0, x
1, x
2, …, x
tsuch that
1.x= x
0;
2.y= x
t; and
3.x
i x
i+1is an edge for every i= 0,1,2,…, t -1.

10. A Path from 18 to 12

11. Connected Graphs
A graph G is connectedif there is a path from xto
yfor every distinct pair of vertices in G.

12. A Connected Graph

13. Components of Disconnected
Graphs
When a graph is disconnected (not connected), an
induced subgraph H is called a component of G when:
(1) H is connected; and
(2) there is no connected subgraph of G containing the
vertex set of H and having more vertices than H.

14. A Disconnected Graph with
3 components

15. Cycles in Graphs
A cyclein a graph G (from xto y) is a
sequence x
0, x
1, x
2, …, x
tof distinct vertices
from G with t≥ 2such that
1.x= x
0;
2.y= x
t; and
3.x
i x
i+1is an edge for every i= 0,1,…, t -1;
4.x
tx
0is an edge.

16. Lenth of Paths and Cycles
When(x
0, x
1, x
2, …, x
t) is a path, there are t+1
vertices in the sequence, but we say that the lengthof
the path is t. This counts the number of edges.
For a positive integer n, it is customary to denote a path
on nvertices as P
n. The length of P
nis then n-1.
When(x
0, x
1, x
2, …, x
t) is a cycle, there are t+1
vertices in the sequence, but now we say that the length
of the cycle is t+1. This again counts the number of
edges since the last vertex is also adjacent to the first.
For a positive integer n, it is customary to denote a
cycle on nvertices as C
n. The length of C
nis then n.

17. A cycle of length 8

18. Complete and Independent Graphs

19. Cliques in Graphs
A set S of vertices in a graph G is called a cliquewhen every
distinct pair of vertices in S is adjacent.
A clique in G is just a set of vertices that induces a complete
subgraph of G.
The maximum clique size of G is denoted by ω(G).

20. Triangles in Graphs
A clique of size 3 is called a triangle.
{1,2,8} is a triangle, but ω(G) = 4

21. ω(G) = 6

22. Caution: Are we certain that
ω(G) = 6
To show that ω(G) ≥ 6, it is enough to show that G
contains a clique of size 6.
But how do we show that G does not contain a clique of
size 7 without testing every subset S consisting of 7
vertices of G? If G contains 34824125 vertices, this
could take a long time!

23. Determining ω(G)
Alice claims that ω(G) = 257. How does she verify
this claim for a graph G with 10342 vertices?
Can you write C code that will accept a graph data
file as input and output a text file, which has ω(G) as
an integer on the first line followed by ω(G) integers,
one per line, immediately below? If you can do this
and have your algorithm run in time which is
polynomial in the input size, then you are guaranteed
an A++ in this course!! Pleaseshare your code with
Professor Trotter before going public.

24. Independent Sets in Graphs
A set S of vertices in a graph G is called an
independentset (also a stableset) when no distinct pair
of vertices in S is adjacent in G.
The maximum size of an independent set of vertices in
G is called the independence number of G and is
denoted α(G).

25. α(G) = 12

26. Are you certain that α(G) = 12
Same caution as before. We have shown only that
α(G) ≥ 12. It requires much more work to show
that G does not contain an independent set of size
13.

27. Graph Coloring
A t-coloringof a graph is a function fwhich assigns to
each vertex xan integer f(x) from {1,2,…,t} so that
f(x) ≠ f(y) whenever xyis an edge of G.
The chromatic number of G, denoted Χ(G), is the least
positive integer tfor which G has a t–coloring.

28. A 6 -Coloring
This shows that Χ(G) ≤ 6

29. Χ(G) ≤ 4

30. A Trivial Inequality
Χ(G) ≥ ω(G)
The chromatic number of a graph is at least as large as
the maximum clique size.

31. Χ(G) = ω(G) = 4

32. How Good is this Inequality?
Χ(G) ≥ ω(G)
Maybe, just maybe, the chromatic number of a graph is
always equal to the maximum clique size?!

33. Not Always Equal
3 = Χ(G) > ω(G) = 2

34. Very large Χ and small ω
Theorem.For every t≥ 3, there exists a graph G
t
so that
Χ(G) = tand ω(G) = 2

35. Posets and Cover Graphs
Cover graphs of posets are triangle-free, i.e., ω(G) ≤ 2

36. Height and Chromatic Number
If G is the cover graph of a poset P with
height (P) = h,
then:
Χ(G) ≤ h
Since any partition of P into hantichains is also a
coloring of G using h colors.

37. Posets and large Χ, small ω
Theorem.For every t≥ 3, there exists a poset P
twith
height (P
t) = t so that if G
tis the cover graph of P
t, then
Χ(G
t) = tand ω(G
t) = 2

38. The First Case
3 = height(P
3) = Χ(G
3) while ω(G
3) = 2
P
3