Book review
elementary Graph Theory & Konigsberg bridge problem & Fundamental Concepts & ( Handshaking Theorem )
Best pdf for students
[Show more]
Seller
Follow
Content preview
Department of Mathematics Elementary Graph Theory Lecture 1Elementary Graph Theory
Introduction
1. Konigsberg bridge problem
Consider this town plan of Konigsberg in East Prussia. The pregel river runs
through the middle of town and a set of 7 bridges links the banks and two
islands in the river. The problem is to find a walk through the town that begins
and ends at the same place, crossing each bridge exactly once.
Euler in 1736 realized that we can simplify the problem by representing it
with this graph, with one edge for each bridge and vertices representing each
islands and each bank.
The problem now is to find a path around the graph which begins and ends at
the same vertex and follows each edge exactly once. Looking at this graph,
Euler was able to show that the problem has no solution.
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 1
2. Paths on a die
To find a circuit on a die visiting each face exactly once we consider this
graph: 1
2
5
6
4 3
There is one vertex for each face and an edge connecting faces. We want
to find a closed circuit on the graph visiting each vertex exactly once. One of
the solution is 1,3,6,4,5,2,1
Fundamental Concepts
Definition: A graph (denoted as G (V, E) ) consists of a non-empty set of
vertices or nodes V and a set of edges or arcs E .
Number of vertices in a graph is called order, usually it is denoted by p or
p(G) .
Number of edges in a graph is called size it is denoted by q or q(G) .
Look at the following graph:
a b z f k
c d h
A graph G
Set of vertices V(G) {a, b,c,d,f , h, k, z} , the order of G , p(G) 8 .
Set of edges E(G) {e1 ,e 2 ,e3 ,e 4 ,e5 ,e6 ,e7 ,e8 ,e9 } , the size of G , q(G) 9
Dr. Didar A. Ali 2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller bilal-guma. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £2.45. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
52928 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now