سعيات المرحلة الاولى لمادة الهياكل المتقطعة

Maps & Regions
? A particular planar representation of a finite planar
multigraph is called a map. We say that the map is
connected if the underlying multigraph is connected.
? A given map divides the plane into various regions.
? By the degree of a region r, written deg(r), we mean the
length of the cycle or closed walk which borders r.
? The sum of the degrees of the
regions of a map is equal to twice
the number of edges
Department of Software 4
edges.
Graph Coloring
? A vertex coloring, or simply a coloring of G is an
assignment of colors to the vertices of G such that adjacent
vertices have different colors.
? We say that G is n-colorable if there exists a coloring of G
which
? The minimum number of colors needed to paint G is called
the chromatic number of G and is denoted by ?(G). uses n
colors.
Department of Software 5
Dual Maps & The Four Color Theorem
? Any planar graph is 4-colorable
Department of Software 6
Welch-Powell Coloring Algorithm
? .
Department of Software 7
Maps & Regions
? A particular planar representation of a finite planar
multigraph is called a map. We say that the map is
connected if the underlying multigraph is connected.
? A given map divides the plane into various regions.
? By the degree of a region r, written deg(r), we mean the
length of the cycle or closed walk which borders r.
? The sum of the degrees of the
regions of a map is equal to twice
the number of edges
Department of Software 4
edges.
Graph Coloring
? A vertex coloring, or simply a coloring of G is an
assignment of colors to the vertices of G such that adjacent
vertices have different colors.
? We say that G is n-colorable if there exists a coloring of G
which
? The minimum number of colors needed to paint G is called
the chromatic number of G and is denoted by ?(G). uses n
colors.
Department of Software 5
Dual Maps & The Four Color Theorem
? Any planar graph is 4-colorable
Department of Software 6
Welch-Powell Coloring Algorithm
? .
Department of Software 7
Maps & Regions
? A particular planar representation of a finite planar
multigraph is called a map. We say that the map is
connected if the underlying multigraph is connected.
? A given map divides the plane into various regions.
? By the degree of a region r, written deg(r), we mean the
length of the cycle or closed walk which borders r.
? The sum of the degrees of the
regions of a map is equal to twice
the number of edges
Department of Software 4
edges.
Graph Coloring
? A vertex coloring, or simply a coloring of G is an
assignment of colors to the vertices of G such that adjacent
vertices have different colors.
? We say that G is n-colorable if there exists a coloring of G
which
? The minimum number of colors needed to paint G is called
the chromatic number of G and is denoted by ?(G). uses n
colors.
Department of Software 5
Dual Maps & The Four Color Theorem
? Any planar graph is 4-colorable
Department of Software 6
Welch-Powell Coloring Algorithm
? .
Department of Software 7