TAILIEUCHUNG - GRAPH THEORY - PART 4

Colourings Edge colourings Colourings của các cạnh và đỉnh của một đồ thị là hữu ích, khi là một trong những quan tâm trong việc phân loại các mối quan hệ giữa các đối tượng. Có hai mặt của chất tạo màu. Trong trường hợp tổng quát, một đồ thị với một màu nhất định, và chúng ta nghiên cứu các tính chất của cặp này «. Đây là tình hình, ví dụ như, trong các mạng giao thông với xe buýt và đào tạo liên kết, màu sắc (hôn, đào tạo) của một cạnh nói với bản chất của. | 4 Colourings Edge colourings Colourings of edges and vertices of a graph G are useful when one is interested in classifying relations between objects. There are two sides of colourings. In the general case a graph G with a colouring is given and we study the properties of this pair G G a . This is the situation . in transportation networks with bus and train links where the colour buss train of an edge tells the nature of a link. In the chromatic theory G is first given and then we search for a colouring that the satisfies required properties. One of the important properties of colourings is properness . In a proper colouring adjacent edges or vertices are coloured differently. Edge chromatic number Definition. A fc-edge colouring a Eg 1 k of a graph G is an assignment ofk colours to its edges. We write G to indicate that G has the edge colouring a. A vertex V E G and a colour i G 1 k are incident with each other if a vu i for some vu E Eg. If u E G is not incident with a colour i then is available for e. The colouring ais proper if no two adjacent edges obtain the same colour a ei 62 j C . dC2 . The edge chromatic number X G ofG is defined as x G min fc I there exists a proper Gedge colouring of G . A fc-edge colouring a can be thought of as a partition Ei. Ẽ2 of 1 G where Eị e I a e i . Note that it is possible that Eị for some i. We adopt a simplified notation G ÙG2 Gt G Eit u u u Eit for the subgraph of G consisting of those edges that have a colour i 1 2 . or ịt. That is the edges having other colours are removed. Lemma . Each colour set Eị in a proper k-edge colouring is a matching. Moreover for each graph G A G xf G g. Proof. This is clear. Edge colourings 44 Example . The three numbers in Lemma can be equal. This happens for instance when G Ki n is a star. But often the inequalities are strict. A star and a graph with G 4. Optimal colourings We show that for bipartite graphs the lower bound is always optimal G Z1 G . Lemma . Let

• Toán học
• toán rời rạc
• biểu diễn đồ thị
• lý thuyết đồ thị
• cơ sở dữ liệu
• thuật toán masyt ính
• biểu diễn cây
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc