GED102 Week 10 WGN - JINGONA

Guided
Noteboo
k in
GED10
Task List
2
T h e g o a l o f t h i
Theory. The discussions will center on the
(Mathe applications and the theoretical treatment of the

subject is deliberately evaded. Those who may be
interested to know more about the topics may read
the reference materials given in the textbook.
matics The topics are grouped into three lessons: Graph

Modelling, Eulerian and Hamiltonian Graphs and
their applications to Weighted Graphs, and Graph
Coloring.
in the Keep track of your progress in this lesson by

checking the number corresponding to each task.
Modern
World)
FIRST QUARTER, SY2020-2021 GED 102 WEEK 10
_____ 1. Watch the introductory video (Module 3 Topic 3 Introduction)
_____ 2. Watch the Youtube videoclip about Konigsberg Problem.
_____ 3. Read/Watch Module 3 Topic 3 Lesson 1 Modelling with Graphs
_____ 4. Work out HW 10 Items #1.
_____ 5. Read/Watch Module 3 Topic 3 Lesson 2 Eulerian and Hamiltonian Graphs
and Weighted Graphs.
_____ 6. Work out HW 10 Items #2 and #3.
_____ 7. Read/Watch Module 3 Topic 3 Lesson 3 Graph Coloring and Applications
_____ 8. Work out HW 10 Items #4 and #5.
_____ 9. Submit HW 10.
_____ 10. Submit WGN 10.
Lesson 1. Modelling with Graphs
Highlights
A. Give a brief definition of the following:

1. Graph
In math, a graph can be defined as a pictorial representation or a diagram

that represents or values in an organized manner. The points on the graph
often represent the relationship between two or more things
2. Degree of a vertex
In graph theory, the degree (or valency) of a vertex of a graph is the number
of edges that are incident to the vertex, and in a multigraph, loops are
counted twice.
3. Isomorphic graphs
Two graphs which contain the same number of graph vertices connected in
the same way are said to be isomorphic.
B. Give 4 types of graphs and give a brief description (you may describe in
words or just draw a sample graph).
 Null Graph - A null graph is a graph in which there are no edges between
its vertices. A null graph is also called empty graph.
 Directed Graph - A directed graph is a graph in which the edges are
directed by arrows. Directed graph is also known as digraphs.
 Complete Graph - A graph in which every pair of vertices is joined by
exactly one edge is called complete graph. It contains all possible edges.
 Connected Graph - A connected graph is a graph in which we can visit
from any one vertex to any other vertex. In a connected graph, at least
one edge or path exists between every pair of vertices.
Lesson 2. Eulerian and Hamiltonian Graphs, Weighted Graphs
Highlights
A. Define the following:
1. Path, Trail
 A path is a trail in which all vertices (and therefore also all edges) are
distinct
 A trail is a walk in which all edges are distinct.

2. Cycle, Circuit
 A circuit that doesn't repeat vertices is called a cycle.
 A circuit is path that begins and ends at the same vertex.
B. What is Eulerian Graph?
In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge
exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail
that starts and ends on the same vertex.
C. What is Hamiltonian Graph?
A Hamiltonian graph may be defined as- If there exists a closed walk in the
connected graph that visits every vertex of the graph exactly once. (except
starting vertex) without repeating the edges, then such a graph is called as a
Hamiltonian graph.
D. Describe how to solve the Konigsberg Problem.
Consider each blob of land. Each bridge is connected to two blobs of land (that’s
how bridges work). Each blob of land happens to have an odd number of bridges
attached.
Now, let’s consider what a valid walk would look like.
As you go on your walk, you record in a notepad each time you are in a certain
blob of land. For instance, if you start in the most southern end of the city, you
make a note of that (take a photo, buy a souvenir…) and if you find yourself
there again, you increase the tally for the southern sector to two.
For each blob of land there are two cases
(1) this is a section of the city we neither start our walk in, nor do we finish
our walk there
(2) this is a section of the city either start our walk in, or we finish our walk
in, or both.
Clearly, there are at most 2 sections of the city of the second type. We cannot
start in two places at once, nor can we finish in two places at once.
As there are four sections of the city, that means that there are at least two
sections of the city, in our walk, which we neither end nor start in. Let’s pick one
of them.
Whenever we go into that sector, we use up one bridge, and whenever we leave
it we use another. But, each sector has an odd number of bridges attached to it!
That’s a contradiction. To see why, recall that each sector has either 3 bridges,
or it has 5 bridges attached.
If we are in the sector once, we can only use up two of its bridges. If we are in it
twice, we would use up four of its bridges (or run out of bridges, if it only had
three bridges). If we are in it three times, we would require 6 bridges, which we
cannot have. So the requirement that we both enter and leave a sector of the
city which is not our start or our end point contradicts the fact that the number
of connecting bridges is odd for every sector.
Lesson 3. Graph Coloring
Highlights
A. Give a summary of the Greedy Algorithm.
A greedy algorithm is a simple, intuitive algorithm that is used in optimization

problems. The algorithm makes the optimal choice at each step as it attempts to
find the overall optimal way to solve the entire problem. Greedy algorithms are
quite successful in some problems, such as Huffman encoding which is used to
compress data, or Dijkstra's algorithm, which is used to find the shortest path
through a graph.
However, in many problems, a greedy strategy does not produce an optimal

solution. For example, in the animation below, the greedy algorithm seeks to
find the path with the largest sum. It does this by selecting the largest available
number at each step. The greedy algorithm fails to find the largest sum,
however, because it makes decisions based only on the information it has at any
one step, without regard to the overall problem.
B. What is a graph coloring?
In graph theory, graph coloring is a special case of graph labeling; it is an

assignment of labels traditionally called "colors" to elements of a graph subject
to certain constraints. In its simplest form, it is a way of coloring the vertices of
a graph such that no two adjacent vertices are of the same color; this is called a
vertex coloring. Similarly, an edge coloring assigns a color to each edge so that
no two adjacent edges are of the same color, and a face coloring of a planar
graph assigns a color to each face or region so that no two faces that share a
boundary have the same color.

GED102 Week 10 WGN - JINGONA

Uploaded by

Copyright:

Available Formats

GED102 Week 10 WGN - JINGONA

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

GED102 Week 10 WGN - JINGONA

Uploaded by

Copyright:

Available Formats

Guided

(Mathe applications and the theoretical treatment of the

matics The topics are grouped into three lessons: Graph

in the Keep track of your progress in this lesson by

_____ 1. Watch the introductory video (Module 3 Topic 3 Introduction)

_____ 2. Watch the Youtube videoclip about Konigsberg Problem.

_____ 3. Read/Watch Module 3 Topic 3 Lesson 1 Modelling with Graphs

_____ 4. Work out HW 10 Items #1.

_____ 5. Read/Watch Module 3 Topic 3 Lesson 2 Eulerian and Hamiltonian Graphs

and Weighted Graphs.

_____ 6. Work out HW 10 Items #2 and #3.

_____ 7. Read/Watch Module 3 Topic 3 Lesson 3 Graph Coloring and Applications

_____ 8. Work out HW 10 Items #4 and #5.

_____ 9. Submit HW 10.

_____ 10. Submit WGN 10.

Lesson 1. Modelling with Graphs

A. Give a brief definition of the following:

In math, a graph can be defined as a pictorial representation or a diagram

Lesson 2. Eulerian and Hamiltonian Graphs, Weighted Graphs

A. Define the following:

 A trail is a walk in which all edges are distinct.

 A circuit that doesn't repeat vertices is called a cycle.

 A circuit is path that begins and ends at the same vertex.

B. What is Eulerian Graph?

C. What is Hamiltonian Graph?

D. Describe how to solve the Konigsberg Problem.

Now, let’s consider what a valid walk would look like.

For each blob of land there are two cases

Lesson 3. Graph Coloring

A. Give a summary of the Greedy Algorithm.

A greedy algorithm is a simple, intuitive algorithm that is used in optimization

However, in many problems, a greedy strategy does not produce an optimal

B. What is a graph coloring?

In graph theory, graph coloring is a special case of graph labeling; it is an

You might also like