tailieunhanh - INTRODUCTION TO COMPUTER SCIENCE - PART 6

THE GRAPH DATA MODEL Đồ thị là sự khái quát của cây đã được nghiên cứu trong tuần hơn con các mối quan hệ cha mẹ, một cạnh trong một đồ thị có thể đại diện cho bất kỳ quan hệ nhị phân giữa hai đối tượng, mỗi đại diện bởi một nút. Đôi khi chúng ta cần chỉ ra một cách rõ ràng sự chỉ đạo của một mối quan hệ bằng cách sử dụng mũi tên chứ không phải là cạnh. Trong trường hợp này, đồ thị được hướng dẫn và cạnh được gọi là vòng cung. Chính thức, chúng ta có. | INTRODUCTION TO COMPUTER SCIENCE HANDOUT 6. THE GRAPH DATA MODEL K5 K6 Computer Science Department Văn Lang University Second semester -- Feb 2002 Instructor Trăn Đức Quang Major themes 1. Basic Concepts 2. Implementation of Graphs 3. Connected Components of an Undirected Graph Reading Sections and . BASIC CONCEPTS The graph is a generalization of the tree that was studied in the previous week. Rather than parent-child relationships an edge in a graph may represents any binary relationship between two objects each represented by a node. Sometimes we need to indicate explicitly the direction of a relationship by using arrows rather than edges. In this case the graph is directed and edges are called arcs. Formally we can define a directed graph as a set N of nodes and a set A of arcs representing a binary relation on N. Graphs can be drawn as suggested in the figure. 7 34 INTRODUCTION TO COMPUTER SCIENCE HANDOUT 6. THE GRAPH DATA MODEL 1. An arrow from node a to b is written a b or a b. We call a the head of the arc and b the tail. We also say that a is a predecessor of b and conversely b is a successor of a. In the above figure the arc 1 1 tells us that node 1 is both a predecessor and a successor of itself. The arc 1 1 is also called a loop. 2. A path in a directed graph is a list of nodes n1 n2 . . . nk such that there is an arc from each node to the next that is ni ni 1 for i 1 2 . . . k - 1. The length of the path is k - 1 the number of arcs along the path. In the figure there are two paths from node 1 to node 4 one is 1 2 3 4 with length 3 the other is 1 3 4 with length 2. 3. A cycle in a directed graph is a path of length 1 or more that begins and ends at the same node. In the figure the path 4 5 7 4 is a cycle of length 3 the path 1 1 is a cycle of length 1. If a graph has one or more cycle we say the graph is cyclic otherwise it is acyclic. In an undirected graph an edge between two node a and b is denoted by a b . Those nodes are neighbors .