Luận văn Ứng dụng đồ thị trong tin học

Cho đồ thị vô hướng G = và A Í X. a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu: - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp các tập ổn đỉnh trong của của G = . Khi đó ký hiệu a(G) = Max {ùAù / Aẻ L} và a(G) được gọi là số ổn định trong của đồ thị G. Như vậy a(G) là số phần tử của 1 tập ổn định trong cực đại nào đó.

doc11 trang | Chia sẻ: ngtr9097 | Lượt xem: 1703 | Lượt tải: 5download
Bạn đang xem nội dung tài liệu Luận văn Ứng dụng đồ thị trong tin học, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

Các file đính kèm theo tài liệu này:

  • docLVANCH2.DOC
  • rarBAOCAO.rar
  • docBttat.doc
  • rarCAIDAT.rar
  • docLVANCH3.DOC
  • docLVANCH4.DOC
  • docLVANCH5.DOC
  • docMuc luc.doc
  • rarNdLVan.rar
  • docPALLVAN1.DOC
  • docthe End.doc
  • docThe first.doc
  • docTomTat.doc
  • docTrang Bia LV.doc