Lý thuyết đồ thị - Phần 2

Chia sẻ: Hoàng Danh Long | Ngày: | Loại File: PPT | Số trang:7

0
187
lượt xem
94
download

Lý thuyết đồ thị - Phần 2

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình toán rời rạc chuyên đề lý thuyết đồ thị

Chủ đề:
Lưu

Nội dung Text: Lý thuyết đồ thị - Phần 2

  1. Chương 3. Lý thuyết đồ thị  3.2. Biểu diễn đồ thị 3.2.1. Các hình thức biểu diễn  Biểu diễn hình học  Biểu  diễn  hình  học  là  một  minh  họa  trực  quan  về  đồ thị, trong đó mỗi đỉnh được coi là một điểm, còn  cạnh  (cung)  là  một  đường  (kèm  theo  mũi  tên)  nối  từ đỉnh nọ đến đỉnh kia.  Tuy  nhiên  BDHH  có  một  nhược  điểm  là  không  được  hỗ  trợ  bởi  các  công  cụ  tính  toán  (máy  tính).  Nó chỉ giúp định hướng (trực quan) cho tư duy trên  đồ thị.     
  2. 3.2. Biểu diễn đồ thị  Danh sách kề  Là danh sách gồm 2 cột. Cột đầu liệt kê tất cả các đỉnh của đồ thị.  Trên  mỗi  dòng  của  cột  thứ  hai  lần  lượt  liệt  kê  các  đỉnh  liền  kề  với  đỉnh tương ứng trong cột thứ nhất.  Một cách lưu trữ danh sách kề là dùng các danh sách liên kết, trong  đó node đầu tiên của mỗi danh sách được cất trong một mảng được  chỉ số hóa bởi các đỉnh.  Ví dụ: 1 2 3 5 1 2 3 5 3 4 2 1 3 5 2 1 3 5 3 1 2 4 3 1 2 4 4 3 5 6 4 3 5 6 1 6 5 1 2 4 6 5 1 2 4 6 2 5 6 4 5 6 4 5    
  3. 3.2. Biểu diễn đồ thị  Danh sách cạnh (cung)  Ví dụ: 1 3  Danh  sách  cạnh  (cung)  của  đồ  thị  có  n  cạnh  (cung)  là  1 5 danh sách gồm n dòng và 2  cột. Mỗi dòng tương ứng với  1 2 một  cạnh  (cung)  của  đồ  thị.  3 4 Trên  mỗi  dòng,  cột  đầu  ghi  3 4 đỉnh  (đỉnh  đầu),  cột  thứ  hai  ghi  đỉnh  kề  (đỉnh  cuối)  của  3 2 cạnh, (cung) tương ứng. 1 6 4 6  Một  cách  lưu  trữ  danh  sách  cạnh là dùng danh sách liên  2 5 4 5 kết,  trong  đó  mỗi  node  tương  ứng  với  một  cạnh  2 5 (cung). 5 6    
  4. 3.2. Biểu diễn đồ thị  Ma trận kề  Cho G   V,   =( E) là một đồ thị có n đỉnh, trong đó tập  đỉnh đã được sắp thứ tự (mã hóa từ 1 đến n).  Ma trận kề của đồ thị là ma trận A=[aik], trong đó  aik là số cạnh (cung) nối từ đỉnh thứ i đến đỉnh thứ  k.  Một số tính chất đơn giản của ma trận kề:  Ma trận kề của một đồ thị là ma trận vuông cấp n.  Nếu đồ thị là đồ thị vô hướng thì ma trận kề là ma trận đối  xứng.  Nếu đồ thị là đơn đồ thị thì ma trận kề là ma trận 0­1.    
  5.  Ví dụ:Đa đồ thị sau 3 4 0 1 1 2 0 1 0  0 2 0 1 0  2 2 0 1 0 0 A=  1 6 0 0 1 0 3 1 1 1 0 3 0 1   5 Có ma trận kề là: 2 0 0 0 1 1 0     Ví dụ:Đơn đồ thị sau 3 4 0 1 1 0 1 0 0 0 1 0 0 0   0 0 0 1 0 0 1 6 A=  0 0 0 0 1 0 0 1 0 0 0 1   2 5  Có ma trận kề là:     0  0 0 1 0 0 
  6.  Ma trận liên thuộc  Cho G=(V,E) là một đồ thị có m đỉnh và  n cạnh (cung). Ma trận liên thuộc tương  ứng với đồ thị là ma trận A cỡ m× n,  trong đó chỉ số của các dòng là chỉ số  đỉnh, và chỉ số của các cột là chỉ số  cạnh; các phần tử aik của ma trận là:    
  7. 3.2.2. Sự đẳng cấu giữa các đồ thị  Định nghĩa  Bất biến đẳng cấu    
Đồng bộ tài khoản