Let’s begin with some problems for which there are polynomial-time algorithms. Suppose you are given a graph on $$n$$ vertices and asked whether or not the graph is connected. Here a positive answer can be justified by providing a spanning tree. On the other hand, a negative answer can be justified by providing a partition of the vertex sets $$V=V_1\cup V_2$$ with $$V_1$$ and $$V_2$$ non-empty subsets and having no edges with one end-point in $$V_1$$ and the other in $$V_2\text{.}$$ In Chapter 12 we will discuss two efficient algorithms that find spanning trees in connected graphs. They can easily be modified to produce a partition showing the graph is disconnected.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9412473,"math_prob":0.998295,"size":2187,"snap":"2023-40-2023-50","text_gpt3_token_len":450,"char_repetition_ratio":0.11268896,"word_repetition_ratio":0.044568244,"special_character_ratio":0.20393233,"punctuation_ratio":0.0721393,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9994913,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-10-03T20:02:16Z\",\"WARC-Record-ID\":\"<urn:uuid:e725d39b-d3c6-4291-8ded-17fe9ac7b329>\",\"Content-Length\":\"68628\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:006d3bf7-c3d9-496f-9097-904cd442170d>\",\"WARC-Concurrent-To\":\"<urn:uuid:4f62f42e-baf7-4ff9-bb6d-10a25629584e>\",\"WARC-IP-Address\":\"70.32.23.119\",\"WARC-Target-URI\":\"https://www.appliedcombinatorics.org/book/s_graphs_complexity.html\",\"WARC-Payload-Digest\":\"sha1:IGP7GXEW3WMQJHZP27T4YAUKG57VJTOC\",\"WARC-Block-Digest\":\"sha1:WUQIE6LOB7PPVI7Z6HNGCPJLVH34CPN6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233511220.71_warc_CC-MAIN-20231003192425-20231003222425-00277.warc.gz\"}"}