tailieunhanh - Giáo trình Toán rời rạc: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Tiếp nội dung phần 1, Giáo trình Toán rời rạc: Phần 2 cung cấp cho người học những kiến thức như: Các khái niệm cơ bản của lý thuyết đồ thị biểu diễn đồ thị trên máy tính, các thuật toán tìm kiếm trên đồ thị và ứng dụng, đồ thị euler và đồ thị hamilton, cây và cây khung của đồ thị bài toán đường đi ngắn nhất; . | Ch- ng 6 c c kh i niÖm c b n cña lý thuyÕt å thÞ biÓu diÔn å thÞ trªn m y tÝnh . C c kh i niÖm c b n cña lý thuyÕt å thÞ Lý thuyÕt å thÞ lµ mét lÜnh vùc -îc nghiªn cøu tõ l u vµ cã nhiÒu øng dông hiÖn i. Ch ng h n å thÞ cã thÓ sö dông Ó x c Þnh c c m ch vßng trong vÊn Ò gi i tÝch m ch iÖn. Chóng ta cã thÓ ph n biÖt hai hîp chÊt ho häc cã cïng c ng thøc ph n tö nh-ng cã cÊu tróc kh c nhau nhê å thÞ. Chóng ta còng cã thÓ x c Þnh xem hai m y tÝnh trong m ng cã thÓ trao æi th ng tin -îc víi nhau hay kh ng nhê m h nh å thÞ cña m ng m y tÝnh. å thÞ víi c c träng sè -îc g n cho c c c nh cña nã cã thÓ dïng Ó gi i c c bµi to n nh- bµi to n t m -êng i ng n nhÊt gi a hai thµnh phè trong mét m ng giao th ng. Chóng ta còng cßn sö dông å thÞ Ó gi i c c bµi to n vÒ lËp lÞch thêi kho biÓu vµ ph n chia kªnh cho c c µi truyÒn h nh. . Þnh nghÜa å thÞ å thÞ lµ mét cÊu tróc rêi r c bao gåm c c Ønh vµ c c c nh nèi c c Ønh ã. Chóng ta ph n biÖt c c lo i å thÞ kh c nhau bëi kiÓu vµ sè l-îng c nh nèi c c cÆp Ønh cña å thÞ. NhiÒu bµi to n thuéc nh ng lÜnh vùc rÊt kh c nhau cã thÓ gi i -îc b ng m h nh å thÞ. Ch ng h n ng-êi ta cã thÓ dïng å thÞ Ó biÓu diÔn kÕt qu cña cuéc thi Êu thÓ thao. Chóng ta còng sÏ chØ ra r ng cã thÓ dïng å thÞ Ó gi i c c bµi to n nh- bµi to n tÝnh sè tæ hîp kh c nhau cña c c chuyÕn bay gi a hai thµnh phè trong mét m ng hµng kh ng hay Ó gi i bµi to n ng-êi du lÞch hoÆc bµi to n t m sè mµu cÇn thiÕt Ó t c c vïng kh c nhau cña mét b n å . Þnh nghÜa . n å thÞ v h-íng G V E bao gåm mét tËp kh ng rçng V lµ tËp c c Ønh vµ mét tËp E lµ tËp c c cÆp kh ng cã thø tù gåm hai phÇn tö kh c nhau cña V gäi lµ c c c nh. 101 VÝ dô . Gi sö mét m ng m y tÝnh gåm c c m y tÝnh vµ c c -êng iÖn tho i. Ta cã thÓ biÓu diÔn vÞ trÝ cña mçi m y tÝnh b ng mét iÓm vµ mçi -êng iÖn tho i b ng mét cung nh- trong h nh . HuÕ Hµ néi TP HCM Nam Þnh µ N ng H i Phßng Th i Nguyªn H nh Trong m ng m y tÝnh nµy ta thÊy cã nhiÒu nhÊt mét -êng iÖn tho i gi a hai m y mçi -êng ho t éng theo c