Giáo trình "Toán rời rạc - Trường CĐ Cơ điện Hà Nội" có nội dung chính gồm 5 chương. Chương 1: Lý thuyết tổ hợp; Chương 2: Các khái niệm cơ bản của lý thuyết đồ thị; Chương 3: Biểu diễn đồ thị và các thuật toán tìm kiếm; Chương 4: Cây và cây khung của đồ thị; Chương 5: Bài toán đường di ngắn nhất. Mời các bạn cùng tham khảo! | Tr-êng Cao ng C iÖn Hµ Néi Ch- ng 1. Lý thuyÕt tæ hîp . S l-îc vÒ tæ hîp Tæ hîp lµ mét phÇn quan träng cña to n häc rêi r c chuyªn nghiªn cøu sù s p xÕp c c èi t-îng chñ Ò nµy -îc nghiªn cøu tõ thÕ kû 17. Khi nh ng trß ch i may rñi liÖt kª Õm c c èi t-îng cã nh ng tÝnh chÊt nµo ã lµ mét phÇn quan träng cña lý thuyÕt tæ hîp. VÝ dô ta dïng quy t c Õm Ó tÝnh tÊt c c c sè iÖn tho i cã thÓ cã trªn toµn n-íc Mü sè mËt khÈu cho phÐp truy nhËt hÖ m y tÝnh liÖt kª c c thø tù vÒ Ých kh c nhau cña c c vËn éng viªn cã thÓ x y ra trong cuéc ch y thi. Mét bµi to n kh c trong lý thuyÕt tæ hîp lµ viÖc t o ra c c c ch s p xÕp theo mét kiÓu nµo ã. VÊn Ò nµy rÊt quan träng trong c c m pháng m y tÝnh. . Quy t c céng Gi sö cã hai c ng viÖc. ViÖc thø nhÊt cã thÓ lµm b ng n1 c ch viÖc thø hai cã thÓ lµm b ng n2 c ch vµ nÕu hai viÖc nµy kh ng thÓ lµm ång thêi khi ã sÏ cã n1 n2 c ch lµm mét trong hai viÖc ã. VÝ dô1 Gi sö cÇn chän hoÆc lµ mét c n bé cña khoa tin hoÆc lµ mét sinh viªn tin lµm i biÓu trong héi ång cña mét tr-êng. Hái cã bao nhiªu c ch chän vÞ i biÓu nµy nÕu khoa tin cã 37 c n bé vµ 83 sinh viªn . Chóng ta më r ng quy t c céng cho tr-êng hîp cã nhiÒu h n hai c ng viÖc. Gi sö c c viÖc T1 T2 Tm cã thÓ lµm t- ng øng b ng n1 n2 nm c ch vµ gi sö kh ng cã hai viÖc nµo ã cã thÓ lµm ång thêi. Khi ã sè c ch lµm mét trong m viÖc ã lµ n1 n2 . nm. VÝ dô2 Mét sinh viªn cã thÓ chän bµi thùc hµnh m y tÝnh tõ mét trong ba danh s ch t- ng øng cã 23 15 vµ 19 bµi. Cã bao nhiªu c ch chän bµi thùc hµnh . Quy t c céng cã thÓ ph t biÓu d-íi d ng ng n ng tËp hîp nh- sau NÕu A1 A2 Am lµ c c tËp rêi nhau khi ã sè phÇn tö cña hîp c c tËp hîp Khoa C ng NghÖ Th ng Tin 1 Tr-êng Cao ng C iÖn Hµ Néi nµy b ng tæng sè c c phÇn tö cña c c tËp thµnh phÇn. A1 A2 . Am A1 A2 . Am . Quy t c nh n Gi sö nhiÖm vô nµo ã -îc t ch ra lµm hai viÖc. ViÖc thø nhÊt cã thÓ lµm b ng n1 c ch viÖc thø hai cã thÓ lµm b ng n2 c ch sau khi thùc hiÖn viÖc thø nhÊt lµm khi ã sÏ cã n1 n 2 c ch thùc hiÖn nhiÖm vô nµy. VÝ .