{"id":160302,"date":"2023-09-25T15:38:48","date_gmt":"2023-09-25T10:08:48","guid":{"rendered":"https:\/\/www.gkseries.com\/blog\/?p=160302"},"modified":"2023-09-25T15:38:48","modified_gmt":"2023-09-25T10:08:48","slug":"let-g-be-a-simple-undirected-graph-let-td-be-a-depth-first-search-tree-of-g","status":"publish","type":"post","link":"https:\/\/www.gkseries.com\/blog\/let-g-be-a-simple-undirected-graph-let-td-be-a-depth-first-search-tree-of-g\/","title":{"rendered":"Let G be a simple undirected graph. Let TD be a depth first search tree of G"},"content":{"rendered":"\n

Q. Let G <\/em>be a simple undirected graph. Let TD <\/em>be a depth first search tree of G<\/em>. Let TB <\/em>be a breadth first search tree of G<\/em>.\u00a0 Consider the following statements.<\/p>\n\n\n\n

I . No edge of G <\/em>is a cross edge with respect to TD<\/em>. (A cross edge in G <\/em>is between two nodes neither of which is an ancestor of the other in TD<\/em>.)<\/p>\n\n\n\n

II. For every edge (u,v<\/em>) of G, <\/em>if u <\/em>is at depth i <\/em>and v <\/em>is at depth j <\/em>in TB<\/em>, then |\ud835\udc56 \u2212 \ud835\udc57| = 1. Which of the statements above must necessarily be true?<\/p>\n\n\n\n

(A) I only                                                       (B) II only<\/p>\n\n\n\n

(C) Both I and II\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (D) Neither I nor II<\/p>\n\n\n\n

Ans: I only<\/p>\n\n\n\n

Sol:<\/p>\n\n\n\n

Undirected graph cant have cross edges in DFS forest. Hence statement 1 is TRUE. Using triangle graph we can counter the second statement.<\/p>\n","protected":false},"excerpt":{"rendered":"

Q. Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G.\u00a0 Consider the following statements. I . No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes […]<\/p>\n","protected":false},"author":419,"featured_media":160303,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[5141],"tags":[5140],"class_list":["post-160302","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-gate","tag-gate-questions"],"_links":{"self":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160302","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/users\/419"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/comments?post=160302"}],"version-history":[{"count":1,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160302\/revisions"}],"predecessor-version":[{"id":160304,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160302\/revisions\/160304"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media\/160303"}],"wp:attachment":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media?parent=160302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/categories?post=160302"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/tags?post=160302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}