Example for Berge's theorem on matching

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite












I'm reading about Berge's theorem on matching, but I think I misunderstood the theorem and definitions somehow, because I cannot make sense of the example below. In this example I've marked the matching in pink, and the alternating path in green. This is the only alternating path involving the matching that I could find, and it's clearly not an augmenting path.



enter image description here



I've realized that there is a bigger matching that could be obtained by taking out edge 3 and adding in edges 1 and 2. But since 1325679 is not an alternating path, shouldn't that possibility not be considered by the theorem?



=============================================



Here are the relevant theorem and definitions:



enter image description here



enter image description here




graph-theory proof-explanation matching-theory




share|cite|improve this question


























    up vote
    1
    down vote

    favorite












    I'm reading about Berge's theorem on matching, but I think I misunderstood the theorem and definitions somehow, because I cannot make sense of the example below. In this example I've marked the matching in pink, and the alternating path in green. This is the only alternating path involving the matching that I could find, and it's clearly not an augmenting path.



    enter image description here



    I've realized that there is a bigger matching that could be obtained by taking out edge 3 and adding in edges 1 and 2. But since 1325679 is not an alternating path, shouldn't that possibility not be considered by the theorem?



    =============================================



    Here are the relevant theorem and definitions:



    enter image description here



    enter image description here




    graph-theory proof-explanation matching-theory




    share|cite|improve this question
























      up vote
      1
      down vote

      favorite









      up vote
      1
      down vote

      favorite











      I'm reading about Berge's theorem on matching, but I think I misunderstood the theorem and definitions somehow, because I cannot make sense of the example below. In this example I've marked the matching in pink, and the alternating path in green. This is the only alternating path involving the matching that I could find, and it's clearly not an augmenting path.



      enter image description here



      I've realized that there is a bigger matching that could be obtained by taking out edge 3 and adding in edges 1 and 2. But since 1325679 is not an alternating path, shouldn't that possibility not be considered by the theorem?



      =============================================



      Here are the relevant theorem and definitions:



      enter image description here



      enter image description here




      graph-theory proof-explanation matching-theory




      share|cite|improve this question














      I'm reading about Berge's theorem on matching, but I think I misunderstood the theorem and definitions somehow, because I cannot make sense of the example below. In this example I've marked the matching in pink, and the alternating path in green. This is the only alternating path involving the matching that I could find, and it's clearly not an augmenting path.



      enter image description here



      I've realized that there is a bigger matching that could be obtained by taking out edge 3 and adding in edges 1 and 2. But since 1325679 is not an alternating path, shouldn't that possibility not be considered by the theorem?



      =============================================



      Here are the relevant theorem and definitions:



      enter image description here



      enter image description here





      graph-theory proof-explanation matching-theory





      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Aug 29 at 11:04

























      asked Aug 29 at 9:47









      ensbana

      296113




      296113




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          2
          down vote













          132 is an augmenting path.



          It is not required that an augmenting path must contain all the edges that are in your matching so far.



          (In fact it doesn't have to contain any edge that is in your matching so far -- say, if you have path graph with four vertices $a-b-c-d$ and start by matching $a$ to $b$, the augmenting path you need to match the other two nodes will consist of the edge $cd$ only).






          share|cite|improve this answer






















          • I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
            – ensbana
            Aug 29 at 10:24






          • 1




            @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
            – Henning Makholm
            Aug 29 at 10:25










          • The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
            – ensbana
            Aug 29 at 22:08






          • 1




            @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
            – Henning Makholm
            Aug 29 at 22:10










          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2898170%2fexample-for-berges-theorem-on-matching%23new-answer', 'question_page');

          );

          Post as a guest

















          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          2
          down vote













          132 is an augmenting path.



          It is not required that an augmenting path must contain all the edges that are in your matching so far.



          (In fact it doesn't have to contain any edge that is in your matching so far -- say, if you have path graph with four vertices $a-b-c-d$ and start by matching $a$ to $b$, the augmenting path you need to match the other two nodes will consist of the edge $cd$ only).






          share|cite|improve this answer






















          • I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
            – ensbana
            Aug 29 at 10:24






          • 1




            @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
            – Henning Makholm
            Aug 29 at 10:25










          • The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
            – ensbana
            Aug 29 at 22:08






          • 1




            @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
            – Henning Makholm
            Aug 29 at 22:10














          up vote
          2
          down vote













          132 is an augmenting path.



          It is not required that an augmenting path must contain all the edges that are in your matching so far.



          (In fact it doesn't have to contain any edge that is in your matching so far -- say, if you have path graph with four vertices $a-b-c-d$ and start by matching $a$ to $b$, the augmenting path you need to match the other two nodes will consist of the edge $cd$ only).






          share|cite|improve this answer






















          • I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
            – ensbana
            Aug 29 at 10:24






          • 1




            @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
            – Henning Makholm
            Aug 29 at 10:25










          • The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
            – ensbana
            Aug 29 at 22:08






          • 1




            @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
            – Henning Makholm
            Aug 29 at 22:10












          up vote
          2
          down vote










          up vote
          2
          down vote









          132 is an augmenting path.



          It is not required that an augmenting path must contain all the edges that are in your matching so far.



          (In fact it doesn't have to contain any edge that is in your matching so far -- say, if you have path graph with four vertices $a-b-c-d$ and start by matching $a$ to $b$, the augmenting path you need to match the other two nodes will consist of the edge $cd$ only).






          share|cite|improve this answer














          132 is an augmenting path.



          It is not required that an augmenting path must contain all the edges that are in your matching so far.



          (In fact it doesn't have to contain any edge that is in your matching so far -- say, if you have path graph with four vertices $a-b-c-d$ and start by matching $a$ to $b$, the augmenting path you need to match the other two nodes will consist of the edge $cd$ only).







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Aug 29 at 10:26

























          answered Aug 29 at 10:18









          Henning Makholm

          230k16296526




          230k16296526











          • I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
            – ensbana
            Aug 29 at 10:24






          • 1




            @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
            – Henning Makholm
            Aug 29 at 10:25










          • The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
            – ensbana
            Aug 29 at 22:08






          • 1




            @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
            – Henning Makholm
            Aug 29 at 22:10
















          • I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
            – ensbana
            Aug 29 at 10:24






          • 1




            @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
            – Henning Makholm
            Aug 29 at 10:25










          • The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
            – ensbana
            Aug 29 at 22:08






          • 1




            @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
            – Henning Makholm
            Aug 29 at 22:10















          I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
          – ensbana
          Aug 29 at 10:24




          I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths?
          – ensbana
          Aug 29 at 10:24




          1




          1




          @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
          – Henning Makholm
          Aug 29 at 10:25




          @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written.
          – Henning Makholm
          Aug 29 at 10:25












          The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
          – ensbana
          Aug 29 at 22:08




          The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching?
          – ensbana
          Aug 29 at 22:08




          1




          1




          @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
          – Henning Makholm
          Aug 29 at 22:10




          @ensbana: Since the definition you quote does not mention any such requirement, it is not required.
          – Henning Makholm
          Aug 29 at 22:10

















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2898170%2fexample-for-berges-theorem-on-matching%23new-answer', 'question_page');

          );

          Post as a guest
































































          -

          這個網誌中的熱門文章

          How to combine Bézier curves to a surface?

          圖片
          Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier cur...
          閱讀完整內容

          Mutual Information Always Non-negative

          圖片
          Clash Royale CLAN TAG #URR8PPP up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 '12 at 15:38 Cameron Buie 83.6k 7 71 154 asked Jun 17 '12 at 15:30 Omri 359 3 13 3 Convexity of the function $tmapsto tlog t$. – Did Jun 17 '12 at 15:33 In addition, the convexity properties require the coefficients in the linear combination sum 1. Then, as p(x,y) is a probability distribution, it fullfits such condition. – Francisco Javier Delgado Ceped Aug 10 at 18:44 add a comment  |  up vote 10 down vote favorite 6 What is the simplest proof that mutual information is always non-negative? i.e., $I(X;Y)ge0$ probability-theory share | cite | improve this question edited Jun 17 ...
          閱讀完整內容

          Why am i infinitely getting the same tweet with the Twitter Search API?

          圖片
          up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia...
          閱讀完整內容