Đồ thị là một cấu trúc dữ liệu quan trọng được nghiên cứu trong Khoa học máy tính. là một chủ đề quan trọng không kém trong cả toán học và Khoa học Máy tính
Biểu diễn đồ thị trong chương trình có nghĩa là tìm cách lưu trữ đồ thị trong bộ nhớ của máy tính. Đó là điều kiện tiên quyết để làm việc với đồ thị trong…
Trước khi chúng tôi bắt đầu triển khai thực tế các biểu đồ trong Python và trước khi bắt đầu giới thiệu các mô-đun Python xử lý các biểu đồ, chúng tôi muốn cống hiến hết mình cho nguồn gốc của lý thuyết đồ thị
Nguồn gốc đưa chúng ta quay ngược thời gian về Künigsberg của thế kỷ 18. Königsberg là một thành phố ở Phổ vào thời điểm đó. Con sông Pregel chảy qua thị trấn, tạo nên hai hòn đảo. Thành phố và các hòn đảo được nối với nhau bằng bảy cây cầu như hình vẽ. Cư dân của thành phố đã rất xúc động trước câu hỏi, liệu có thể đi bộ qua thị trấn bằng cách ghé thăm từng khu vực của thị trấn và chỉ băng qua mỗi cây cầu một lần không? . e. không được phép đi nửa cầu rồi quay lại và sau đó băng qua nửa còn lại từ phía bên kia. Cuộc đi bộ không cần phải bắt đầu và kết thúc tại cùng một điểm. Leonhard Euler đã giải quyết vấn đề vào năm 1735 bằng cách chứng minh rằng không thể
Ông phát hiện ra rằng việc lựa chọn tuyến đường bên trong mỗi vùng đất là không liên quan và điều duy nhất quan trọng là thứ tự [hoặc trình tự] các cây cầu được bắc qua. Ông đã hình thành một cách trừu tượng hóa vấn đề, loại bỏ các sự kiện không cần thiết và tập trung vào các khu vực đất liền và các cây cầu nối chúng với nhau. Bằng cách này, ông đã tạo ra nền tảng của lý thuyết đồ thị. Nếu chúng ta coi một "diện tích đất" là một đỉnh và mỗi cây cầu là một cạnh, chúng ta đã "thu gọn" bài toán thành đồ thị
Đào tạo Python trực tiếp
Thưởng thức trang này?
Thấy. Tổng quan về các khóa học Python trực tiếp
đăng ký tại đây
Giới thiệu về Lý thuyết đồ thị bằng Python
Trước khi bắt đầu thảo luận về các biểu diễn Python có thể có của đồ thị, chúng tôi muốn trình bày một số định nghĩa chung về đồ thị và các thành phần của nó
Một "đồ thị"1 trong toán học và khoa học máy tính bao gồm các "nút", còn được gọi là "đỉnh". Các nút có thể hoặc không thể được kết nối với nhau. Trong hình minh họa của chúng tôi, - là một biểu diễn bằng hình ảnh của biểu đồ,
- nút "a" được kết nối với nút "c", nhưng "a" không được kết nối với "b". Đường nối giữa hai nút gọi là cạnh. Nếu các cạnh giữa các nút là vô hướng thì đồ thị được gọi là đồ thị vô hướng. Nếu một cạnh được hướng từ đỉnh [nút] này sang đỉnh [nút] khác thì đồ thị được gọi là đồ thị có hướng. Cạnh có hướng gọi là cung
Mặc dù đồ thị có thể trông rất lý thuyết, nhưng nhiều vấn đề thực tế có thể được biểu diễn bằng đồ thị. Chúng thường được sử dụng để mô hình hóa các vấn đề hoặc tình huống trong vật lý, sinh học, tâm lý học và trên hết là khoa học máy tính. Trong khoa học máy tính, đồ thị được sử dụng để biểu diễn các mạng truyền thông, tổ chức dữ liệu, thiết bị tính toán, luồng tính toán,
Trong trường hợp sau, chúng được sử dụng để đại diện cho tổ chức dữ liệu, như hệ thống tệp của hệ điều hành hoặc mạng truyền thông. Cấu trúc liên kết của các trang web cũng có thể được xem như một biểu đồ, tôi. e. một đồ thị có hướng, bởi vì một liên kết là một cạnh có hướng hoặc một cung
Python không có kiểu dữ liệu hoặc lớp tích hợp cho biểu đồ, nhưng thật dễ dàng để triển khai chúng trong Python. Một kiểu dữ liệu lý tưởng để biểu diễn đồ thị trong Python, đó là. e. từ điển. Biểu đồ trong hình minh họa của chúng tôi có thể được thực hiện theo cách sau
graph = { "a" : {"c"}, "b" : {"c", "e"}, "c" : {"a", "b", "d", "e"}, "d" : {"c"}, "e" : {"c", "b"}, "f" : {} }
Các khóa của từ điển ở trên là các nút của biểu đồ của chúng tôi. Các giá trị tương ứng được đặt với các nút, được kết nối bởi một cạnh. Một tập hợp tốt hơn một danh sách hoặc một bộ, bởi vì theo cách này, chúng ta chỉ có thể có một cạnh giữa hai nút. Không có cách nào đơn giản và thanh lịch hơn để biểu diễn biểu đồ
Một cạnh cũng có thể được triển khai một cách lý tưởng dưới dạng một tập hợp có hai phần tử, i. e. các nút cuối. Điều này là lý tưởng cho các đồ thị vô hướng. Đối với đồ thị có hướng, chúng tôi thích danh sách hoặc bộ dữ liệu hơn để triển khai các cạnh
Hàm tạo danh sách tất cả các cạnh
def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]
ĐẦU RA
[{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
Như chúng ta có thể thấy, không có cạnh nào chứa nút "f". "f" là một nút bị cô lập trên biểu đồ của chúng tôi. Hàm Python sau tính toán các nút bị cô lập của một biểu đồ đã cho
def find_isolated_nodes[graph]: """ returns a set of isolated nodes. """ isolated = set[] for node in graph: if not graph[node]: isolated.add[node] return isolated
Nếu chúng ta gọi hàm này với biểu đồ của mình, một danh sách chứa "f" sẽ được trả về. ["f"]
Đồ thị dưới dạng Lớp Python
Trước khi chúng ta tiếp tục viết các hàm cho biểu đồ, trước tiên chúng ta sẽ thực hiện triển khai lớp biểu đồ Python
Nếu bạn nhìn vào danh sách sau của lớp chúng ta, bạn có thể thấy trong phương thức init chúng ta sử dụng một từ điển "self. _graph_dict" để lưu trữ các đỉnh và các đỉnh liền kề tương ứng của chúng
""" A Python Class A simple Python graph class, demonstrating the essential facts and functionalities of graphs. """ class Graph[object]: def __init__[self, graph_dict=None]: """ initializes a graph object If no dictionary or None is given, an empty dictionary will be used """ if graph_dict == None: graph_dict = {} self._graph_dict = graph_dict def edges[self, vertice]: """ returns a list of all the edges of a vertice""" return self._graph_dict[vertice] def all_vertices[self]: """ returns the vertices of a graph as a set """ return set[self._graph_dict.keys[]] def all_edges[self]: """ returns the edges of a graph """ return self.__generate_edges[] def add_vertex[self, vertex]: """ If the vertex "vertex" is not in self._graph_dict, a key "vertex" with an empty list as a value is added to the dictionary. Otherwise nothing has to be done. """ if vertex not in self._graph_dict: self._graph_dict[vertex] = [] def add_edge[self, edge]: """ assumes that edge is of type set, tuple or list; between two vertices can be multiple edges! """ edge = set[edge] vertex1, vertex2 = tuple[edge] for x, y in [[vertex1, vertex2], [vertex2, vertex1]]: if x in self._graph_dict: self._graph_dict[x].add[y] else: self._graph_dict[x] = [y] def __generate_edges[self]: """ A static method generating the edges of the graph "graph". Edges are represented as sets with one [a loop back to the vertex] or two vertices """ edges = [] for vertex in self._graph_dict: for neighbour in self._graph_dict[vertex]: if {neighbour, vertex} not in edges: edges.append[{vertex, neighbour}] return edges def __iter__[self]: self._iter_obj = iter[self._graph_dict] return self._iter_obj def __next__[self]: """ allows us to iterate over the vertices """ return next[self._iter_obj] def __str__[self]: res = "vertices: " for k in self._graph_dict: res += str[k] + " " res += "\nedges: " for edge in self.__generate_edges[]: res += str[edge] + " " return res
Chúng tôi muốn chơi một chút với biểu đồ của chúng tôi. Chúng tôi bắt đầu với việc lặp lại trên biểu đồ. Lặp lại có nghĩa là lặp qua các đỉnh
g = { "a" : {"d"}, "b" : {"c"}, "c" : {"b", "c", "d", "e"}, "d" : {"a", "c"}, "e" : {"c"}, "f" : {} } graph = Graph[g] for vertice in graph: print[f"Edges of vertice {vertice}: ", graph.edges[vertice]]
ĐẦU RA
Edges of vertice a: {'d'}
Edges of vertice b: {'c'}
Edges of vertice c: {'c', 'd', 'b', 'e'}
Edges of vertice d: {'c', 'a'}
Edges of vertice e: {'c'}
Edges of vertice f: {}
graph.add_edge[{"ab", "fg"}] graph.add_edge[{"xyz", "bla"}]
________số 8_______
ĐẦU RA
Vertices of graph:
{'d', 'b', 'e', 'f', 'fg', 'c', 'bla', 'xyz', 'ab', 'a'}
Edges of graph:
[{'d', 'a'}, {'c', 'b'}, {'c'}, {'c', 'd'}, {'c', 'e'}, {'ab', 'fg'}, {'bla', 'xyz'}]
Hãy tính danh sách tất cả các đỉnh và danh sách tất cả các cạnh của đồ thị của chúng ta
________số 8_______
ĐẦU RA
Vertices of graph:
{'d', 'b', 'e', 'f', 'fg', 'c', 'bla', 'xyz', 'ab', 'a'}
Edges of graph:
[{'d', 'a'}, {'c', 'b'}, {'c'}, {'c', 'd'}, {'c', 'e'}, {'ab', 'fg'}, {'bla', 'xyz'}]
Chúng tôi thêm một đỉnh và một cạnh vào đồ thị
def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]2
ĐẦU RA
def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]3
def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]4
ĐẦU RA
def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]5
Đào tạo Python trực tiếp
Thưởng thức trang này?
Thấy. Tổng quan về các khóa học Python trực tiếp
đăng ký tại đây
Đường dẫn trong đồ thị
Bây giờ chúng tôi muốn tìm đường đi ngắn nhất từ nút này đến nút khác. Trước khi chúng ta đến với mã Python cho vấn đề này, chúng ta sẽ phải trình bày một số định nghĩa chính thức
đỉnh liền kề
Hai đỉnh kề nhau khi chúng cùng kề một cạnh chung
Đường đi trong đồ thị vô hướng
Đường đi trong đồ thị vô hướng là dãy các đỉnh P = [ v1, v2,. , vn ] ∈ V x V x. x V sao cho vi kề với v{i+1} với 1 ≤ i < n. Đường đi P như vậy được gọi là đường đi có độ dài n từ v1 đến vn
Đường dẫn đơn giản
Đường đi không có đỉnh lặp lại gọi là đường đi đơn
Thí dụ
[a, c, e] là một đường đi đơn giản trong đồ thị của chúng ta, cũng như [a,c,e,b]. [a,c,e,b,c,d] là một đường đi nhưng không phải là đường đi đơn vì nút c xuất hiện hai lần
Chúng tôi thêm một phương thức
[{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
6 vào lớp của chúng tôi [{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
7. Nó cố gắng tìm một đường đi từ đỉnh bắt đầu đến đỉnh kết thúc. Chúng tôi cũng thêm một phương thức [{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
8, tìm tất cả các đường dẫn từ đỉnh bắt đầu đến đỉnh kết thúcdef generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]6
Chúng tôi kiểm tra cách làm việc của các phương pháp
[{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
6 và [{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
8 sau đâydef generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]7
ĐẦU RA
def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]8
Chúng tôi đã thay đổi một chút biểu đồ ví dụ của mình bằng cách thêm các cạnh từ "a" thành "f" và từ "f" thành "d" để kiểm tra phương pháp
[{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
8def generate_edges[graph]: edges = [] for node in graph: for neighbour in graph[node]: edges.append[{node, neighbour}] return edges print[generate_edges[graph]]9
ĐẦU RA
[{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
0Bằng cấp và trình tự Bằng cấp
Bậc của một đỉnh v trong một đồ thị là số cạnh nối với nó, với các vòng lặp được tính hai lần. Bậc của một đỉnh v được ký hiệu là deg[v]. Bậc lớn nhất của đồ thị G, ký hiệu là Δ[G], và bậc nhỏ nhất của đồ thị, ký hiệu là δ[G], là bậc lớn nhất và bậc nhỏ nhất của các đỉnh của nó
Trong đồ thị bên phải, bậc lớn nhất là 5 tại đỉnh c và bậc nhỏ nhất là 0, i. e đỉnh cô lập f
Nếu tất cả các bậc trong một đồ thị đều bằng nhau thì đồ thị đó là đồ thị chính quy
Trong một đồ thị thông thường, tất cả các bậc đều như nhau và vì vậy chúng ta có thể nói về bậc của đồ thị
Công thức tổng bậc [Bổ đề bắt tay]
∑v ∈ Vdeg[v] = 2. E
Điều này có nghĩa là tổng bậc của tất cả các đỉnh bằng số cạnh nhân với 2. Ta có thể kết luận rằng số đỉnh có bậc lẻ phải là số chẵn. Tuyên bố này được gọi là bổ đề bắt tay. Cái tên "bổ đề bắt tay" bắt nguồn từ một bài toán phổ biến. Trong bất kỳ nhóm người nào, số người bắt tay với số lẻ số người khác trong nhóm là số chẵn
Dãy bậc của đồ thị vô hướng được định nghĩa là dãy các đỉnh bậc của nó theo thứ tự không tăng. Phương thức sau đây trả về một bộ có trình tự bậc của biểu đồ thể hiện
Bây giờ chúng ta sẽ thiết kế một lớp mới
def find_isolated_nodes[graph]: """ returns a set of isolated nodes. """ isolated = set[] for node in graph: if not graph[node]: isolated.add[node] return isolated2, kế thừa từ đồ thị đã xác định trước đó của chúng ta là
[{'c', 'a'}, {'c', 'b'}, {'b', 'e'}, {'c', 'd'}, {'c', 'b'}, {'c', 'e'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
7 và chúng ta thêm các phương thức sau vào nó