tailieunhanh - Lí thuyết đồ thị part 2

Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một website có thể được biểu diễn bằng một đồ thị có hướng như sau: các đỉnh là các trang web hiện có tại website, tồn tại một cạnh có hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B. Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm chính. | Tính liên thông Dây chuyền và chu trình Gia sứ v0 vk là các đỉnh của đồ thi vô hướng G V E . Dầy chuyền ạ tu v0 đến độ dài k là một đay xen kẽ k 1 đỉnh và k cạnh bát đau từ Vo và kết thức tại Vk ạ vo ei Vi e2 v2 . Vk-i ek Vk trong đô cạnh ei liến thủộc càc đỉnh vi-i và Vi i 1 2 . k. Đế giàn tiện tà thường viết ạ ei e2 . ek . Độy chuyến được gọi là đơn gian tương ứng sơ cấp nếủ nô không đi hài làn quà củng mết cành tương ứng đỉnh . Chu trình là mết đếy chuyến trọng đá đỉnh đầu trứng vôi đỉnh cuếi. Chu trình quà môi cành đúng mết lần gọi là đơn gian. Chu trình là sơ cấp nếu nô đi quà mếi đỉnh đúng mết lến trừ đỉnh đàu tiến hài làn mết làn luc xuết phàt và mết luc trô vế . Đô thi trông Hành cô a ei b e2 c e3 d e4 b là đày chuyến tír đỉnh a đến đỉnh b cá đế đài bến. Các chu trành sàu là sơ cếp b e2 c e3 d e4 b và b e5 f e7 e e6 b . Hàỉnh Trông trường hợrp đế thi không cá canh sơng sơng tức là hài đỉnh cô nhiếu nhàt mết cành liến thuôc chung đế đơn giàn đày chuyến ạ được viết lài ạ vo Vi V2 . Vk . 23 Dường đi và mạch Gia sử v0 vk là các đỉnh của đồ thi có hướng G V E . Dường đi g tù v0 đến vk độ dài k là một đày xen kẽ k 1 đỉnh và k cung bắt đàù tù v0 và kết thùc tài Vk g vo ei Vi e2 v2 . vk-1 ek Vk trong đá cung ei liến thuộc càc đỉnh vi-1 và vị i 1 2 . k. Đế giàn tiện tà cá thế ky hiộu đường đi g là e1 e2 . ek . Đo đá trong Hình đẽy các cung g1 66 65 69 68 64 g2 ei e6 e5 e9 g3 61 66 65 69 610 66 64 là càc đường đi. Đường đi là đơn gian nếu khồng chứà cung nào quà một lộn. Suy rà càc đường đi g1 g2 là đơn giàn nhưng đường đi g3 không đơn giàn đo ná sử đung cung e6 hài lộn. Đường đi là sơ cap nếu khếng đi quà đỉnh nào quà một lộn. Khi đó đường đi g2 là sơ cộp nhưng càc đường đi g1 và g3 là khếng sơ cấp. Hiến nhiên đường đi sơ cộp là đơn giàn nhưng ngược lài không nhàt thiết đúng. Chàng hàn chu y rằng đường đi g1 là đơn giàn nhưng khong sơ cộp đường đi g2 vừà đơn giàn và vừà sơ cộp đường đi g3 khộng đon giàn cung khộng so càp. Chu y ràng .