eBook - ePub
Graph Theory
Undergraduate Mathematics
Khee Meng Koh, Fengming Dong, Kah Loon Ng;Eng Guan Tay
This is a test
Partager le livre
- 496 pages
- English
- ePUB (adapté aux mobiles)
- Disponible sur iOS et Android
eBook - ePub
Graph Theory
Undergraduate Mathematics
Khee Meng Koh, Fengming Dong, Kah Loon Ng;Eng Guan Tay
DĂ©tails du livre
Aperçu du livre
Table des matiĂšres
Citations
Ă propos de ce livre
This book is an expansion of our first book Introduction to Graph Theory: H3 Mathematics. While the first book was intended for capable high school students and university freshmen, this version covers substantially more ground and is intended as a reference and textbook for undergraduate studies in Graph Theory. In fact, the topics cover a few modules in the Graph Theory taught at the National University of Singapore. The reader will be challenged and inspired by the material in the book, especially the variety and quality of the problems, which are derived from the authors' years of teaching and research experience.
Request Inspection Copy
Contents:
- Fundamental Concepts and Basic Results
- Graph Isomorphisms, Subgraphs, the Complement of a Graph and Graphic Sequences
- Bipartite Graphs and Trees
- Eulerian Multigraphs and The Chinese Postman Problem
- Hamiltonian Graphs and The Traveling Salesman Problem
- Connectivity
- Independence, Matching and Covering
- Vertex-colorings and Planar Graphs
- Domination
- Digraphs and Tournaments
Readership: Undergraduates in combinatorics and graph theory.
Key Features:
- The coverage includes some frontier research and this can encourage readers to engage in some research themselves
- The set of problems is extensive and some are cutting-edge
- Not intended for the average Joe in Mathematics
Foire aux questions
Comment puis-je résilier mon abonnement ?
Il vous suffit de vous rendre dans la section compte dans paramĂštres et de cliquer sur « RĂ©silier lâabonnement ». Câest aussi simple que cela ! Une fois que vous aurez rĂ©siliĂ© votre abonnement, il restera actif pour le reste de la pĂ©riode pour laquelle vous avez payĂ©. DĂ©couvrez-en plus ici.
Puis-je / comment puis-je télécharger des livres ?
Pour le moment, tous nos livres en format ePub adaptĂ©s aux mobiles peuvent ĂȘtre tĂ©lĂ©chargĂ©s via lâapplication. La plupart de nos PDF sont Ă©galement disponibles en tĂ©lĂ©chargement et les autres seront tĂ©lĂ©chargeables trĂšs prochainement. DĂ©couvrez-en plus ici.
Quelle est la différence entre les formules tarifaires ?
Les deux abonnements vous donnent un accĂšs complet Ă la bibliothĂšque et Ă toutes les fonctionnalitĂ©s de Perlego. Les seules diffĂ©rences sont les tarifs ainsi que la pĂ©riode dâabonnement : avec lâabonnement annuel, vous Ă©conomiserez environ 30 % par rapport Ă 12 mois dâabonnement mensuel.
Quâest-ce que Perlego ?
Nous sommes un service dâabonnement Ă des ouvrages universitaires en ligne, oĂč vous pouvez accĂ©der Ă toute une bibliothĂšque pour un prix infĂ©rieur Ă celui dâun seul livre par mois. Avec plus dâun million de livres sur plus de 1 000 sujets, nous avons ce quâil vous faut ! DĂ©couvrez-en plus ici.
Prenez-vous en charge la synthÚse vocale ?
Recherchez le symbole Ăcouter sur votre prochain livre pour voir si vous pouvez lâĂ©couter. Lâoutil Ăcouter lit le texte Ă haute voix pour vous, en surlignant le passage qui est en cours de lecture. Vous pouvez le mettre sur pause, lâaccĂ©lĂ©rer ou le ralentir. DĂ©couvrez-en plus ici.
Est-ce que Graph Theory est un PDF/ePUB en ligne ?
Oui, vous pouvez accĂ©der Ă Graph Theory par Khee Meng Koh, Fengming Dong, Kah Loon Ng;Eng Guan Tay en format PDF et/ou ePUB ainsi quâĂ dâautres livres populaires dans MathĂ©matiques et MathĂ©matiques discrĂštes. Nous disposons de plus dâun million dâouvrages Ă dĂ©couvrir dans notre catalogue.
Informations
Sujet
MathématiquesSous-sujet
Mathématiques discrÚtesChapter 1
Fundamental Concepts and Basic
Results
1.1The Königsberg Bridge Problem
The River Pregel flowed through the old city of Königsberg in 18th century Eastern Prussia. Back then, there were seven bridges over the river connecting the two islands (B and D) and two opposite banks (A and C) as shown in Fig. 1.1.1.
It was said that the people in the city had always amused themselves with the following problem:
Starting with any one of the four places A, B, C or D as shown in Fig. 1.1.1, is it possible to have a walk which passes through each of the seven bridges once and only once, and return to where you started?
No one could find such a walk; and after a number of tries, people believed that it was simply not possible, but no one could convincingly prove it either.
Leonhard Euler, the greatest mathematician that Switzerland has ever produced, was told of the problem. He noticed that the problem was very much different in nature from the problems in traditional geometry, and instead of considering the original problem, he studied its much more general version which encompassed any number of islands or banks, and any number of bridges connecting them. His finding was contained in the article Euler (1736). As a direct consequence of his finding, he deduced the impossibiity of having such a walk in the Königsberg bridge problem. This was historically the first time a proof was given from the mathematical point of view.
How did Euler generalize the Königsberg bridge problem? How did he solve his more general problem? What was his finding?
1.2Multigraphs and Graphs
Euler observed that the Königsberg bridge problem had nothing to do with traditional geometry where the measurements of lengths and angles, and relative locations of vertices count. How large the islands and banks are, how long the bridges are, and whether an island is at the south or north of a bank are immaterial. The key ingredients are whether the islands or banks are connected by a bridge, and by how many bridges.
Eulerâs idea was essentially as follows: represent the islands or banks by âdotsâ, one for each island or bank, and two dots are joined by k âlinesâ (not necessarily straight), where k â„ 0, when and only when the respective islands or banks represented by the dots are connected by k bridges. Thus the situation for the Königsberg bridge problem is represented by the diagram in Fig. 1.2.1.
The diagram in Fig. 1.2.1 is now known as a multigraph. Int...