eBook - ePub
Graph Theory
Ronald Gould
This is a test
Partager le livre
- 352 pages
- English
- ePUB (adapté aux mobiles)
- Disponible sur iOS et Android
eBook - ePub
Graph Theory
Ronald Gould
DĂ©tails du livre
Aperçu du livre
Table des matiĂšres
Citations
Ă propos de ce livre
This introduction to graph theory focuses on well-established topics, covering primary techniques and including both algorithmic and theoretical problems. The algorithms are presented with a minimum of advanced data structures and programming details. This thoroughly corrected 1988 edition provides insights to computer scientists as well as advanced undergraduates and graduate students of topology, algebra, and matrix theory.
Fundamental concepts and notation and elementary properties and operations are the first subjects, followed by examinations of paths and searching, trees, and networks. Subsequent chapters explore cycles and circuits, planarity, matchings, and independence. The text concludes with considerations of special topics and applications and extremal theory. Exercises appear throughout the text.
Fundamental concepts and notation and elementary properties and operations are the first subjects, followed by examinations of paths and searching, trees, and networks. Subsequent chapters explore cycles and circuits, planarity, matchings, and independence. The text concludes with considerations of special topics and applications and extremal theory. Exercises appear throughout the text.
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 Ronald Gould en format PDF et/ou ePUB ainsi quâĂ dâautres livres populaires dans Mathematics et Discrete Mathematics. Nous disposons de plus dâun million dâouvrages Ă dĂ©couvrir dans notre catalogue.
Informations
Sujet
MathematicsSous-sujet
Discrete MathematicsChapter 1
Graphs
Section 1.0 Introduction
For years, mathematicians have affected the growth and development of computer science. In the beginning they helped design computers for the express purpose of simplifying large mathematical computations. However, as the role of computers in our society changed, the needs of computer scientists began affecting the kind of mathematics being done.
Graph theory is a prime example of this change in thinking. Mathematicians study graphs because of their natural mathematical beauty, with relations to topology, algebra and matrix theory spurring their interest. Computer scientists also study graphs because of their many applications to computing, such as in data representation and network design. These applications have generated considerable interest in algorithms dealing with graphs and graph properties by both mathematicians and computer scientists.
Today, a study of graphs is not complete without at least an introduction to both theory and algorithms. This text will attempt to convince you that this is simply the nature of the subject and, in fact, the way it was meant to be treated.
Section 1.1 Fundamental Concepts and Notation
Graphs arise in many settings and are used to model a wide variety of situations. Perhaps the easiest way to adjust to this variety is to see several very different uses immediately. Initially, letâs consider several problems and concentrate on finding models representing these problems, rather than worrying about their solutions.
Suppose that we are given a collection of intervals on the real line, say C = { I1, I2, . . . , Ik}. Any two of these intervals may or may not have a nonempty intersection. Suppose that we want a way to display the intersection relationship among these intervals. What form of model will easily display these intersections?
One possible model for representing these intersections is the following: Let each interval be represented by a circle and draw a line between two circles if, and only if, the intervals that correspond to these circles intersect. For example, consider the set
C = { [â4, 2], [0, 1], (â8, 2], [2, 4], [4, 10) }.
The model for these intervals is shown in Figure 1.1.1.
Next, we consider the following old puzzle. Suppose there are three houses (call them h1, h2 and h3) and three utility companies (say gas (g), water (w) and electricity (e)). Our problem is to determine if it is possible to connect each of the three houses to each of the three utilities without crossing the service lines that run from the utilities to the houses. We model this puzzle by representing each house and each utility as a circle and drawing a line between two circles if there is a service line between the corresponding house and utility. We picture this situation in Figure 1.1.2. A solution to this problem would be a drawing in which no lines crossed. The drawing of Figure 1.1.2 is not a solution to the problem, but merely an attempt at modeling the problem.
In our third problem, suppose you are the manager of a company that has four job openings (say j1, j2, j3 and j4) and five applicants a1, . . . , a5 and that some of these applicants are qualified for more than one of your jobs. How do you go about choosing people to fill the jobs so that you will fill as many openings as possible? We picture such a situation in Figure 1.1.3. Again, each job and each applicant can be represented as a circle. This time, a line is drawn from a circle represe...