Содержание
- 2. Definitions and examples
- 3. Definitions and examples Euler (1707 – 1783) was born in Switzerland and spent most of his
- 4. Definitions and examples Like many of the very great mathematicians of his era, Euler contributed to
- 5. Definitions and examples What is a ‘graph’? Intuitively, a graph is simply a collection of points,
- 6. Definitions and examples
- 7. Definitions and examples
- 8. Definitions and examples
- 9. Definitions and examples
- 10. Definitions and examples
- 11. Definitions and examples Definition 2 The degree sequence of a graph is the sequence of its
- 12. Definitions and examples
- 13. Definitions and examples
- 14. Definitions and examples The degrees of the four vertices are given in the following table.
- 15. Definitions and examples
- 16. Definitions and examples A well known 3-regular simple graph is Peterson’s graph. Two diagrams representing this
- 17. Definitions and examples
- 18. Definitions and examples Example 1 Since a complete graph is simple there are no loops and
- 19. Definitions and examples
- 20. Definitions and examples Example 1 The complete graphs with three, four and five vertices are illustrated
- 21. Definitions and examples
- 22. Definitions and examples
- 23. Definitions and examples
- 24. Definitions and examples
- 25. Definitions and examples
- 26. Definitions and examples
- 27. Definitions and examples
- 28. Definitions and examples
- 29. Definitions and examples
- 30. Definitions and examples
- 31. Definitions and examples
- 32. Definitions and examples Example 4 A complete graph has adjacency matrix with zeros along the leading
- 33. Definitions and examples
- 34. Definitions and examples
- 35. Paths and cycles Using the analogy of a road map, we can consider various types of
- 36. Paths and cycles
- 37. Paths and cycles
- 38. Paths and cycles
- 39. Paths and cycles An edge sequence is any finite sequence of edges which can be traced
- 40. Paths and cycles Edge sequences are too general to be of very much use which is
- 41. Paths and cycles In a path we are not allowed to ‘travel along’ the same edge
- 42. Paths and cycles If, in addition, we do not ‘visit’ the same vertex more than once
- 43. Paths and cycles The edge sequence or path is closed if we begin and end the
- 44. Paths and cycles
- 45. Paths and cycles
- 46. Paths and cycles
- 47. Paths and cycles
- 48. Paths and cycles
- 49. Paths and cycles
- 50. Paths and cycles
- 51. Paths and cycles
- 52. Paths and cycles
- 53. Paths and cycles
- 55. Paths and cycles
- 56. Paths and cycles
- 57. Paths and cycles
- 58. Paths and cycles
- 59. Paths and cycles In an intuitively obvious sense, some graphs are ‘all in one piece’ and
- 60. Paths and cycles Definition 7 A graph is connected if, given any pair of distinct vertices,
- 61. Paths and cycles An arbitrary graph naturally splits up into a number of connected subgraphs, called
- 62. Paths and cycles
- 63. Paths and cycles The components of a graph are just its connected ‘pieces’. In particular, a
- 64. Paths and cycles
- 65. Paths and cycles
- 66. Paths and cycles
- 67. Paths and cycles
- 69. Скачать презентацию