Please enable JavaScript.

Coggle requires JavaScript to display documents.

Toán rời rạc (Graph (Định nghĩa (2 graph equal (Nếu có thể rename 1 tên…

- - - - Removing a single edge from a connected graph can make it
        disconnected
    - - Là đồ thị phẳng nếu các cạnh không cắt xen nhau, trừ ở đỉnh ( nếu có thể vẽ lại và các cạnh ko cắt nhau thì vẫn là đồ thị phẳng )
    - - Đồ thị liên thông nếu có thể đi từ đỉnh này đến đỉnh kia qua
        các cạnh
    - - Đẳng cấu giữa 2 tập hợp là 1 song ánh f : V1 -> V2 sao cho nếu a,b là 1 cạnh của G1 thì f (a) f (b) là 1 cạnh của G2. 2 Đồ thị đẳng cấu nếu có 1 đẳng cáu giữa chúng
    - - Các cặp cạnh đều giống nhau với các tên đỉnh giống nhau
      - Nếu có thể rename 1 tên đỉnh của cả 2 graph thành song ánh ==>
        
        2 Đồ thị đẳng cấu ( isomorphic )
    - - bề mặt ( tính cả trong lẫn bên ngoài)
    - - 1 đồ thị G chứa V (G) tập các đỉnh và E (G) tập các cạnh
  - - - 1 . Chắc chắn đồ thị có 0 hoặc 2 đỉnh lẻ
      - 2 . Nếu có 0 đỉnh lẻ. Bắt đầu ở đâu cũng đc. Nếu có 2 đỉnh lẻ, bắt đầu từ chúng
      - 3 . Đi theo các cạnh. If you have a choice : bridge vs non-bridge, always choose non-bridge
      - 4 . Đi đến kết thúc
- - - - Xuất phát từ điểm
    - - Xuất phát từ cạnh
    - - Chọn các điểm theo thứ tự
- - - - Phức hợp
        
        Xây dựng từ các mệnh đề khác =
        
        liên từ, "không"
      - Sơ cấp
        
        Không thể xây dựng từ các mệnh đề khác
    - - Nếu luôn giá trị 1 và ngược lại
    - - Nếu vs mỗi A thuộc X có p(a) là mệnh đề đúng , thì khẳng định "Vs mọi x thuộc X, p(x)" là mệnh đề đúng
  - - - Đúng khi p và q đều đúng
    - - Sai khi cả q và p đều sai
    - - Sai khi p đúng - > q sai
        
        Nếu..... Thì
    - - p và q cùng chân trị
  - - - p -> q, nếu có p thì có q
    - - Nếu p -> q, ko q thì sẽ ko p
    - - p or q, ko p --> thì q
    - - (p1 AND p2 AND p3) -> q <=>
      - p1 AND p2 AND p3 AND ko q -> 0
- - - - Tính toán
        
        Bool 2 biến
        
        Có 2 ^ 2 = 4 phần tử
        
        Có 2 ^ 2 = 16 hàm bool
        
        Bool 3 biến
        
        Có 2 ^ 3 = 8 phần tử
        
        Có 2^ 8 hàm boole
        
        Bool n biến
        
        Có 2 ^ n phần tử
        
        Có 2 ^ 2 ^ n hầm boole
    - - Giao hoán
        
        x + y = y + x
        
        x . y = y . x
      - Kết hợp
        
        (x+y) + z = x+(y+z)
        
        (x.y).z = x.(y.z)
      - Phân phối
        
        z.(x+y) = z.x + z.y
        
        z + (x.y) = (z + x) . (z + y)
      - Phần tử đơn vị
        
        x + 0 = x
        
        x.1 = x
      - Phần bù
        
        x + x' = 1
        
        x . x' = 0
      - ∼(A.B)=∼A+∼B
        ∼(A+B)=∼A.∼B
    - - AND là "."
      - OR là "+"
  - - - Tổng các tích từ tối tiểu
        
        VD: xyz + x'y'z'
    - - Bước 1: Vẽ biểu đồ karnaugh của f.
      - Bước 2: Xác định tất cả các tế bào lớn của kar(f)
      - Bước 3: Xác định các tế bào lớn nhất thiết phải chọn Ta nhất thiết phải chọn tế bào lớn T. Khi tồn tại 1 ô của kar mà ô này chỉ nằm trong tb lớn T chứ ko nằm trong bất kỳ tb lớn nào khác
      - Bước 4: Xác định các phủ tối tiểu gồm các tb lớn
        
        • Nếu các tế bào lớn chọn được ở bước 3 đã phủ được kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tb lớn. • Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được kar(f) thì:
        
        Tiếp tục
        
        Các công thức còn lại, chọn công thức đơn giản nhất. Hoàn thành
        
        Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của kar(f)
        
        Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này