Trong luận án này, chúng tôi điều chỉnh các phần cơ bản của loạt Graph Minors của Robertson và Seymour để nghiên cứu các phép ghép nhỏ và tìm hiểu mối liên hệ với nghiên cứu đồ thị có hướng. Chúng tôi phát triển lý thuyết ghép cho các kết quả đã thiết lập của lý thuyết đồ thị nhỏ: Chúng tôi mô tả sự tồn tại của phép giao trên một chu trình đồng dạng bằng một tính chất tôpô. Hơn nữa, chúng tôi phát triển một lý thuyết về độ rộng ghép hoàn hảo, một tham số độ rộng cho đồ thị có phép ghép hoàn hảo do Norin giới thiệu. Ở đây, chúng tôi chỉ ra rằng bài toán đường đi xen kẽ rời rạc có thể được giải trong thời gian đa thức trên đồ thị có độ rộng bị chặn. Hơn nữa, chúng tôi chỉ ra rằng mọi đồ thị hai phần có độ rộng ghép hoàn hảo cao phải chứa một lưới lớn làm phép ghép nhỏ. Cuối cùng, chúng tôi chứng minh một phép tương tự của định lý Flat Wall đã biết và cung cấp mô tả định tính về tất cả các đồ thị hai phần loại trừ phép ghép nhỏ cố định.

Abstract:

In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width must contain a large grid as a matching minor. Finally, we prove an analogue of the we known Flat Wall theorem and provide a qualitative description of all bipartite graphs which exclude a fixed matching minor.

Ngôn ngữ:	eng
Tác giả:	Schulz, Daniel, Bauckhage, Christian
Thông tin nhan đề:	Informed Machine Learning
Nhà xuất bản:	Springer Nature
Loại hình:	Tài nguyên giáo dục mở / Bộ sưu tập: Công nghệ thông tin
Bản quyền:	http://creativecommons.org/licenses/by/4.0/
Nguồn gốc:	https://directory.doabooks.org/handle/20.500.12854/158451
Mô tả vật lý:	339p.
Năm xuất bản:	2025